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.
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.Sign up to join this community
Here is an example.
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.
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.