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

1 Answer 1

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
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

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.