Colouring graphs on surfaces
type: Item
instance of: scholarly article
zbMATH Open document ID: 1362.05049
author: Bojan Mohar
publication date: 2016-09-30T00:00:00Z
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C10
zbMATH DE Number: 6632104
zbMATH Keywords: four-color theorem
zbMATH Keywords: list coloring
zbMATH Keywords: Heawood theorem
zbMATH Keywords: \(k\)-critical graph
zbMATH Keywords: locally planar graph
zbMATH Keywords: nowhere-zero flow
zbMATH Keywords: circular coloring
zbMATH Keywords: acyclic coloring
zbMATH Keywords: degenerate coloring
zbMATH Keywords: star coloring
MaRDI profile type: Publication
title: Colouring graphs on surfaces
review text: This chapter contains a comprehensive survey of classical milestones in graph theory related to the problems of graph coloring, with particular emphasis on some recent and more specialized coloring results and problems.NEWLINENEWLINENEWLINEThe survey starts with a short historical review and the motivation for consideration of the questions about coloring graphs on surfaces. The role of the famous four-color theorem (Every planar graph is 4-colorable.) is highlated. At the beginning we find a complete proof of a Thomassen's result (Every planar graph is 5-list colorable.), a sketch of the proof of the four-color theorem, and some related results about coloring and list-coloring of planar graphs.NEWLINENEWLINEThe first result about coloring graphs on surfaces is the Heawood formula (an analogue of the four-color theorem): If a graph \(G\) is embedded in a surface \(S\) of Eulerian genus \(g\), then NEWLINENEWLINE\[NEWLINE\chi(G)\leqslant\lfloor\frac1 2 (7+\sqrt{1+24g})\rfloor= H(g).NEWLINE\]NEWLINE NEWLINEHeawood conjectured that in the above inequality, the equality holds for all surfaces. Ringel and Youngs verified that this conjecture is true in all cases except for the Klein bottle. This text gives a proof of the Heawood inequality and a detailed discussion about the proof of Heawood's conjecture using a result by Dirac about \(k\)-critical graphs.NEWLINENEWLINEThe next section considers \(k\)-critical graphs embeddable on a surface. For all \(k>6\), there are only finitely many obstructions for \((k-1)\)-coloring of a graph embedded on a surface, and therefore there exists a polynomial time algorithm for testing whether this graph is \((k-1)\)-colorable. Among other results, we can find here a list of all 6-critical toroidal graphs and the statement that for each surface \(S\) there is a finite list of 6-critical graphs embeddable on \(S\) (these results are due to Thomassen). A result of Fisk implies that there is no similar statement for 5-critical graphs.NEWL…
reviewed by: Duško Jojić
description: scientific article; zbMATH DE number 6632104