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?
3
$\begingroup$
graph-theory
coloring
-
0Well, 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
-
2http://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
-
1Which 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
-
04CC = 4 Colour Theorem – 2012-02-07
-
0I 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
-
0I 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
-
0Ah, okay, that seems clear enough now. – 2012-02-08
-
0Was my answer helpful? – 2012-03-14