Take the 2-minute tour ×
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.

Is it possible to have a planar graph with a chromatic number of $4$ such that all vertices have degree $4$?

Every time I try to make the degree condition to work on a graph, it loses its planarity.

share|improve this question

2 Answers 2

up vote 8 down vote accepted

Here is an example.

enter image description here

The graph is 4 regular and 4 colorable. However, it's not possible to color its vertices with 3 colors. The picture shows a partial coloring that cannot be extended to the whole graph.

share|improve this answer
    
Is it a problem that there are two black adjacent vertices? –  apnorton Dec 8 '13 at 22:15
    
@anorton, the coloring was incorrect. I fixed it. –  Yury Dec 9 '13 at 20:06
1  
Actually, this image doesn't show the 4 coloring. It shows a partial 3-coloring that cannot be extended to a valid 3-coloring of the entire graph. It's not hard to color the graph in 4 colors. –  Yury Dec 9 '13 at 20:09
    
Ah-ok. That makes sense. –  apnorton Dec 9 '13 at 21:31

Gerhard Koester in 1985 constructed infinitely many planar 4-regular graphs that not only are 4-chromatic, but also 4-critical, that is, all their proper subgraphs are 3-colorable.

The only planar 3-regular 4-critical graphs is the complete graph of order 4, by Brooks's Theorem. Curiously it is known that no 5-regular planar graph is 4-critical. But I am not aware of any proof that every 5-regular planar graph is 4-colorable, without using the Four Color Theorem.

share|improve this answer

Your Answer

 
discard

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.