Resumen de Distance constraints in graph color extensions
Joan P. Hutchinson, Emily H. Moore
Let G be an r-chromatic graph with an s-colorable subgraph, each of whose components is s-colored with (possibly different) s colors taken from a set of r+s colors. Then if the components of the precolored subgraph are sufficiently far apart, the precoloring extends to an (r+s)-coloring of G. We determine in all cases the best possible distance bounds between precolored components that allow for this extension result. Next suppose that G is Kr+1-minor-free for r=2,3,4, or 5 (and so is r-colorable by proven cases of Hadwiger's Conjecture). Then similarly to the first result there is an extension of a precoloring of a subgraph, each component of which receives s colors from a set of r+s-1, to an (r+s-1)-coloring of the whole graph; we determine bounds on the distance between precolored components that ensures this extension. We include some open problems in this area, building on our joint work with M.O. Albertson.
