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) -> N such that for any two consecutive colors, the edges joining the colors form a matching. The minimum positive integer t for which there exists a semi-matching coloring c : V (G) -> {1,2, ... , t} is called the semi-matching chromatic number of G and denoted by chi(m)(G). In view of Tucker-Ky Fan's lemma, we show that chi(m)(KG(n, k)) = 2 chi(KG(n, k)) - 2 = 2n - 4k + 2 provided that n <= 8/3k. 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 chi(m)(KG(n, k)) >= max(2 chi(KG(n, k)) - 10, chi(KG(n, k))), where n >= 2k >= 4. Also, for n >= 2k >= 4, we conjecture that chi(m)(KG(n, k)) = 2 chi(KG(n, k)) - 2. (C) 2011 Elsevier B.V. All rights reserved.