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.
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
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.
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.