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.
[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.