On 3-coloring some more planar graphs and 3- and 4-coloring some graphs on surfaces
by
Joan P. Hutchinson
Macalester College
Coauthors: B. Richter, P. Seymour

It is well-known (and easy to prove) that a planar graph can be 2-colored if and only if every face is even-sided, and that a planar triangulation can be 3-colored if and only if each vertex has even degree. We consider analogous graphs on surfaces and their chromatic numbers. Inspired by C. Thomassen's theorem that every graph, embedded on a surface with all noncontractible cycles sufficiently long, can be 5-colored, we discuss a new proof of Theorem 1. A graph embedded on an orientable surface with all faces even-sided and all noncontractible cycles sufficiently long can be 3-colored, and of Theorem 2. An even-degreed triangulation of an orientable surface, embedded with all noncontractible cycles sufficiently long, can be 4-colored.

These results do not extend to nonorientable surfaces, and give the best possible chromatic number bounds for these classes of embedded graphs. We also present the latest related results for nonorientable surfaces, and we return to the plane, where the proof of Theorem 2 leads to some new 3-color results.

Date received: October 23, 2000