Grötzsch's 3-color theorem and its counterparts for the torus and the projective plane
type: Item
instance of: scholarly article
title: Grötzsch's 3-color theorem and its counterparts for the torus and the projective plane
zbMATH Open document ID: 0817.05024
published in: Journal of Combinatorial Theory. Series B
publication date: 1994-11-29T00:00:00Z
review text: 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.
reviewed by: Marietjie Frick
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C10
zbMATH DE Number: 696912
zbMATH Keywords: torus
zbMATH Keywords: projective plane
zbMATH Keywords: graph embeddings
zbMATH Keywords: planar graph
zbMATH Keywords: Grötzsch's theorem
zbMATH Keywords: 3-colour theorem
zbMATH Keywords: toroidal graph
author: Carsten Thomassen
MaRDI profile type: Publication
full work available at URL: jctb.1994.1069
OpenAlex ID: W2008383657
DOI: 10.1006/JCTB.1994.1069
description: scientific article; zbMATH DE number 696912