# Are there any results on the chromatic number of planar regular graphs not using the 4CC?

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.

-
Well, trivially any $n$-regular graph can be $(n+1)$-colored, so what kind of theorem were you expecting for the 4-regular case? – Henning Makholm Feb 6 '12 at 1:31
– Ricky Demer Feb 6 '12 at 3:01
@Henning I was looking for a better upper bound if available. I'm aware of the 5CC and the trivial case you mentioned. And by 4CC I mean the actual general proof of the 4CC. So proofs for special cases/subsets of planar graphs are still allowed if they provide an upper bound for the regular graph case in the question. Thanks. – asja Feb 6 '12 at 8:49
Which meaning of 4CC are you referring to? And how much effort is it to expand the acronym at least once? – Marc van Leeuwen Feb 6 '12 at 12:39
4CC = 4 Colour Theorem – asja Feb 7 '12 at 0:27

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.

-