Let $c_k$ be the maximum chromatic number that a $k$-regular graph can have. What is $\lim\sup_{k\to\infty}\frac{c_k}{k}$?
$\begingroup$
$\endgroup$
5
asked Jan 16, 2019 at 14:49
-
3$\begingroup$ Uh, the chromatic number is bounded by the maximal degree plus one, so $c_k\leq k+1$, but conversely the complete graph on $k+1$ vertices shows that $c_k\geq k+1$. What did I miss? $\endgroup$– Gro-TsenCommented Jan 16, 2019 at 15:18
-
2$\begingroup$ I would also like to mention the upper bound can be easily shown with a greedy algorithm, no need to appeal to any theorems for just that. $\endgroup$– WojowuCommented Jan 16, 2019 at 17:29
-
7$\begingroup$ @Dominic: In the past 10 days, you've asked 11 questions and currently the average vote on them is lower than 1 positive vote. I think you should think a little bit more about your questions before posting them, or consider posting some of them on math.stackexchange.com. This is particularly true of your questions in graph theory (or perhaps I just know more about this area); many, if not most of them, admit examples/counterexamples of very small order that could be found by anyone who actually spent a few minutes thinking about it. $\endgroup$– verretCommented Jan 16, 2019 at 19:52
-
$\begingroup$ @verret I absolutely agree - my apologies $\endgroup$– Dominic van der ZypenCommented Jan 16, 2019 at 20:18
-
2$\begingroup$ I'm voting to close this question for the reasons pointed out ib @verret's comment $\endgroup$– Yemon ChoiCommented Jan 16, 2019 at 22:44
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.$$
answered Jan 16, 2019 at 15:13