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.


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.

  • 1
    $\begingroup$ Is it a problem that there are two black adjacent vertices? $\endgroup$ – apnorton Dec 8 '13 at 22:15
  • $\begingroup$ @anorton, the coloring was incorrect. I fixed it. $\endgroup$ – Yury Dec 9 '13 at 20:06
  • 2
    $\begingroup$ 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. $\endgroup$ – Yury Dec 9 '13 at 20:09
  • $\begingroup$ Ah-ok. That makes sense. $\endgroup$ – apnorton Dec 9 '13 at 21:31
  • $\begingroup$ This graph is more symmetric than it looks, by the way. It's the graph of a square antiprism, and is vertex-transitive. $\endgroup$ – Henning Makholm Jul 13 '18 at 12:03

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.