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