1
$\begingroup$

In other words, can a planar graph without k3 have a chromatic number larger than 3?

1 Answers 1

4

Yes, every triangle-free planar graph is 3-colorable. This is known as Grötzsch's theorem.

  • 1
    It is perhaps worth noting that the theorem does not generalize in the natural way, as evidenced in answers to this question: http://math.stackexchange.com/questions/225872/can-a-graph-be-non-3-colourable-without-having-k4-as-a-sub-graph2012-11-01