Are there any theorems regarding the chromatic number of planar regular graphs of degree 4 and 5 that do not rely on the 4CC? Please provide a reference if possible. Thanks.
Are there any results on the chromatic number of planar regular graphs not using the 4CC?
-
0Was my answer helpful? – 2012-03-14
1 Answers
The book "Graphs and Digraphs", Fifth Edition, by Chartrand, Lesniak, and Zhang contains a section called "Bounds for the Chromatic Number". Here are the two results that seem to best fit what you're asking for. They don't use planarity at all.
Theorem
For every graph $G$, $\chi(G) \leq 1 + \Delta(G).$
Theorem
For every connected graph $G$ that is not an odd cycle or a complete graph, $\chi(G) \leq \Delta(G).$
So, for a regular connected graph with vertex degree 4 (assuming it's not a $K_5$, and it's definitely not a cycle based on the degree), we know that it can be colored with at most 4 colors. And, for one with vertex degree 5 (assuming it's not a $K_6$), it can be colored with at most 5 colors. Of course, the second theorem could be extended to non-connected graphs so long as none of the components are odd cycles or complete graphs.