0
$\begingroup$

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.

$\endgroup$
0

2 Answers 2

11
$\begingroup$

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.

$\endgroup$
4
  • 2
    $\begingroup$ Is it a problem that there are two black adjacent vertices? $\endgroup$
    – apnorton
    Dec 8, 2013 at 22:15
  • 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, 2013 at 20:09
  • $\begingroup$ Ah-ok. That makes sense. $\endgroup$
    – apnorton
    Dec 9, 2013 at 21:31
  • 1
    $\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$ Jul 13, 2018 at 12:03
2
$\begingroup$

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.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .