A generalization of Kneser’s conjecture

We investigate some coloring properties of Kneser graphs. A semi-matching coloring is a proper coloring c:V(G)→Nc:V(G)→N such that for any two consecutive colors, the edges joining the colors form a matching. The minimum positive integer tt for which there exists a semi-matching coloring c:V(G)→{1,2,…,t}c:V(G)→{1,2,…,t} is called the semi-matching chromatic number of GG and denoted by χm(G)χm(G). In view of Tucker–Ky Fan’s lemma, we show that χm(KG(n,k))=2χ(KG(n,k))−2=2n−4k+2 provided that n≤83k. This gives a partial answer to a conjecture of Omoomi and Pourmiri [Local coloring of Kneser graphs, Discrete Mathematics, 308 (24): 5922–5927, (2008)]. Moreover, for any Kneser graph KG(n,k), we show that χm(KG(n,k))≥max{2χ(KG(n,k))−10,χ(KG(n,k))}, where n≥2k≥4n≥2k≥4. Also, for n≥2k≥4n≥2k≥4, we conjecture that χm(KG(n,k))=2χ(KG(n,k))−2.