Given a positive integer $n\in \mathbb{N}$, is there a positive integer $k\in{\mathbb N}$ such that
for every finite, simple, undirected graph $G$ with $\Delta(G) = n$ we have $\chi(G) \leq k$
?
$\begingroup$
$\endgroup$
asked Sep 25, 2017 at 5:50
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
$k=n+1$. For the coloring with $n+1$ colors, use induction on the number of vertices.
answered Sep 25, 2017 at 6:01
$\begingroup$
$\endgroup$
2
By Brooks's theorem, one can take $k=n$ when the graph (assumed to be connected) is not isomorphic to $K_p$ (the complete graph on $p$ vertices), and $C_p$ (the cycle on $p$ vertices), $p$ odd.
answered Sep 25, 2017 at 6:31
-
$\begingroup$ to be rigorous, this is for connected graphs $\endgroup$ Commented Sep 25, 2017 at 7:25
-
$\begingroup$ You're right ! I corrected my message. $\endgroup$ Commented Sep 25, 2017 at 9:19