3
$\begingroup$

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.

  • 0
    Well, trivially any $n$-regular graph can be $(n+1)$-colored, so what kind of theorem were you expecting for the 4-regular case?2012-02-06
  • 2
    http://www.proofwiki.org/wiki/Five_Color_Theorem $\:$2012-02-06
  • 0
    @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.2012-02-06
  • 1
    Which meaning of [4CC](http://en.wikipedia.org/wiki/4CC) are you referring to? And how much effort is it to expand the acronym at least once?2012-02-06
  • 0
    4CC = 4 Colour Theorem2012-02-07
  • 0
    I don't really get what you mean at all. You say don't use the 4 color theorem, but then in the comment it seems like what you really mean is you want a BETTER bound than 4 colors. If what you really want is a better bound than the 4 color theorem, you should say, "I am looking for a bound that is even better than the 4 color theorem" and not "I want a bound not using the 4 color theorem". The second question can be answered by Henning and by Ricky as they did. The first can not be answered by either.2012-02-07
  • 0
    I can see how it might be confusing. I'll try again. Basically, is there a result (perhaps obtained before the 4CC was proven) that uses different techniques to the 4CC to find a bound on the chromatic number specifically for regular planar graphs (or some superset of these graphs) that is better than the obvious n+1.2012-02-07
  • 0
    Ah, okay, that seems clear enough now.2012-02-08
  • 0
    Was my answer helpful?2012-03-14

1 Answers 1

2

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.