A Generalization of Kneser's Conjecture

Abstract

We investigate some coloring properties of Kneser graphs. A star-free coloring is a proper coloring $c:V(G)\to \mathbb{N}$ such that no path with three vertices may be colored with just two consecutive numbers. The minimum positive integer $t$ for which there exists a star-free coloring $c:V(G)\to \{1,2,...,t\}$ is called the star-free chromatic number of $G$ and denoted by ${\chi }_s(G)$. In view of Tucker-Ky Fan's lemma, we show that for any Kneser graph $\mathrm{KG}(n,k)$ we have ${\chi }_s(\mathrm{KG}(n,k))\ge \max \{2\chi (\mathrm{KG}(n,k))-10,\chi (\mathrm{KG}(n,k))\}$ where $n\ge 2k\ge 4$. Moreover, we show that ${\chi }_s(\mathrm{KG}(n,k))=2\chi (\mathrm{KG}(n,k))-2=2n-4k+2$ provided that $n\le \frac{8}{3}k$. This gives a partial answer to a conjecture of [12]. Also, we conjecture that for any positive integers $n\ge 2k\ge 4$ we have ${\chi }_s(\mathrm{KG}(n,k))=2\chi (\mathrm{KG}(n,k))-2$.