Extending precolorings of subgraphs of graphs embedded on surfaces and in general
by
Joan P. Hutchinson
Macalester College
Coauthors: M. O. Albertson and E. H. Moore

Suppose part of a graph is precolored with "few" colors. When can the precoloring extend to a coloring of the rest of the graph with only a "few more" colors? The answer depends upon the context. We present results in general, for planar graphs, for K₅-minor-free graphs, and for "locally planar" graphs, that is, for graphs embedded on nonplanar surfaces with all noncontractible cycles long. The goal of each result and of each conjecture is to precolor independent vertices, bipartite subgraphs, s-chromatic subgraphs, and then to extend the coloring with the smallest number of additional colors. We discuss related results and conjectures for list-colorings, their precolorings and extensions.

Date received: May 5, 2008