Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
@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.


For every graph $G$, $$\chi(G) \leq 1 + \Delta(G).$$


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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.