Return to Revisions

The complete graph with $k+1$ vertices (which is strongly $k$-regular) has degree $k$ and chromatic number $k+1$. On the other hand, by Brook's theorem this is the maximum possible value for the chromatic number of a $k$-regular graph, so $$\limsup_k \frac{c_k}{k} = \lim_k \frac{c_k}{k}=1.$$