Colouring graphs on surfaces (Q2822588)

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.NEWLINENEWLINEOne of the sections in this chapter begins with a classical theorem by Grötzch (A planar graph without triangles is 3-colorable.) and other related results. Thomassen proved that a planar graph whose girth is at least 5 is 3-list colorable. Hutchinson generalized Grötzch's theorem for arbitrary orientable surface \(S_g\) of genus \(g\). A graph \(G\) embedded on \(S_g\) is 3-colorable if the length of a shortest cycle in \(G\) that is not contractible (the edge-width of \(G\)) is bigger than the constant \(f(g)\) and all facial walks have even length. Youngs shows that a graph, embeddable in the projective plane such that all faces are quadrilaterals, has chromatic number \(2\) or \(4\). Therefore, Hutchinson's result cannot be extended to non-orientabile surfaces. This section also lists some results about \(k\)-critical graphs with bounded girth.NEWLINENEWLINENEWLINETutte introduced the concept of nowhere-zero flow (Chapter 9 in this collection) and proved that for a connected planar graph this is equivalent to coloring of the dual graph. A section in this chapter extended this result to the circular chromatic index and the circular flow index of connected planar graphs. An approximate duality for these indices holds for graphs on an orientable surface if its edge-width is large enough (locally planar graphs). For a similar result for graphs on non-orientable surfaces, one has to define the local circular chromatic index.NEWLINENEWLINEIn this chapter, we also find an overview of results and interesting hypotheses for some special kind of colorings of graphs (acyclic, degenerate, star and degenerate star coloring). At the end of the chapter, all known results about chromatic numbers planar graphs, locally planar graphs and graphs embeddable on a surface of genus \(g\) are collected.NEWLINENEWLINEFor the entire collection see [Zbl 1317.05004].