Distance constraints in graph color extensions

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 K r + 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.