Return to Revisions

Take the Kneser graph $K(2k+r,k)$, defined as the graph where the vertices are the $k$-element subsets of $\{1,2,\dots,2k+r\}$, and there is an edge between two vertices if the corresponding sets are disjoint. It is not hard to prove that we can take any $c < \frac{1}{2+\frac{r}{k}}$, but the chromatic number is $r+2$. So the answer to your question is negative.