Grötzsch's 3-color theorem and its counterparts for the torus and the projective plane (Q1338317): Difference between revisions

Grötzsch proved in 1958 that every planar graph of girth at least 4 is 3-colourable. His proof, which relies on a list of reducible configurations, is rather long. There have been several attempts at providing shorter proofs but, until now, these proofs have been either incorrect or not significantly shorter. In this paper the author succeeds in providing a short proof of Grötzsch's theorem. His proof relies on a 3-colour theorem for planar graphs of girth 5 with a prescribed 3- colouring of the outer cycle. The proof of this 3-colour theorem is rather densely written and not very clearly presented, but it can definitely be considered short, and Grötzsch's theorem is a quick corollary of this theorem. The same theorem is then also used to prove two other notable results, namely that every toroidal graph of girth at least 5 is 3-coloured (a best possible result in the sense that there are infinitely many toroidal 4-chromatic graphs of girth at least 4) and that every graph in the projective plane with girth at least 5 is 3- colourable.