|
Organizers |
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 K5-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
Copyright © 2008 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # cawn-69.