Grötzsch's theorem

In the mathematical field of graph theory, Grötzsch's theorem is the statement that every triangle-free planar graph can be colored with only three colors.

The theorem is named after German mathematician Herbert Grötzsch, who published its proof in 1959.

Berge (1960) attempted to simplify it but his proof was erroneous.

[1] In 1989, Richard Steinberg and Dan Younger formulated and proved a planar dual version of the theorem: a 3-edge-connected planar graph (or more generally a planar graph with no bridges and at most three 3-edge cuts) has a nowhere-zero 3-flow.

[2] In 2003, Carsten Thomassen[3] derived an alternative proof from another related theorem: every planar graph with girth at least five is 3-list-colorable.

[4] In 2012, Nabiha Asghar[5] gave a new and much simpler proof of the theorem that is inspired by Thomassen's work.

A slightly more general result is true: if a planar graph has at most three triangles then it is 3-colorable.

In 2009, Dvořák, Kráľ, and Thomas announced a proof of another generalization, conjectured in 1969 by L. Havel: there exists a constant

[6] This work formed part of the basis for Dvořák's 2015 European Prize in Combinatorics.

By combining these two results, it may be shown that every triangle-free planar graph has a homomorphism to a triangle-free 3-colorable graph, the tensor product of

[9] A result of de Castro et al. (2002) combines Grötzsch's theorem with Scheinerman's conjecture on the representation of planar graphs as intersection graphs of line segments.

They proved that every triangle-free planar graph can be represented by a collection of line segments, with three slopes, such that two vertices of the graph are adjacent if and only if the line segments representing them cross.

A 3-coloring of the graph may then be obtained by assigning two vertices the same color whenever their line segments have the same slope.