In other words, can a planar graph without k3 have a chromatic number larger than 3?
Is every planar graph without triangles 3-colorable?
1
$\begingroup$
general-topology
graph-theory
coloring
1 Answers
4
Yes, every triangle-free planar graph is 3-colorable. This is known as Grötzsch's theorem.
-
1It 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-graph – 2012-11-01