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