Chapter 8   Colorings of graphs on surfaces

Let G be a graph and k a natural number. A k-coloring of G is a map c that maps the vertices of G into the set {1, 2, ..., k} (whose elements are called colors) such that no two adjacent vertices are mapped to the same color. A graph is k-colorable if it admits a k-coloring. The chromatic number χ(G) of G is equal to the smallest k such that G is k-colorable. Clearly, χ(G) < 3 if and only if G is bipartite. By Konig's theorem, χ(G) < 3 if and only if G has no odd cycle. Since odd cycles are easy to find, one can easily recognize graphs with χ(G) < 3. In contrast to this, it is NP-complete to decide if χ(G) < 4, even for planar graphs, cf. [GJ79].

Graph coloring is one of the central subjects in discrete mathematics. The recent book by Jensen and Toft [JT95] is an excellent reference. In this chapter we focus on coloring graphs on surfaces. In Section 8.2 we describe briefly some of the ideas in the proof of the Four Color Theorem. In Section 8.3 we consider its generalization to general surfaces, known as the Heawood Problem: What is the largest chromatic number of a graph that can be embedded in a given surface. A solution was conjectured by Heawood [He890] and proved by Ringel and Youngs [RY68, Ri74]. The Heawood conjecture reduces to determining the genus and the nonorientable genus of complete graphs. The solution by Ringel and Youngs involves constructions of genus embeddings of these graphs and introduces techniques that can be also used for constructions of small genus embeddings of other graphs (see Chapter 4).

Finally, we outline coloring results and problems of a more specialized nature.

References

[GJ79] M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the Theory of the NP-Completeness, W. H. Freeman, San Francisco, 1979.

[He890] P. J. Heawood, Map-colour theorem, Quart. J. Pure Appl. Math. 24 (1890) 332-338.

[JT95] T. Jensen, B. Toft, Graph Coloring Problems, John Wiley, New York, 1995.

[Ri74] G. Ringel, Map Color Theorem, Springer-Verlag, Berlin, 1974.

[RY68] G. Ringel, J. W. T. Youngs, Solution of the Heawood map-coloring problem, Proc. Nat. Acad. Sci. U.S.A. 60 (1968) 438-445.