Extending graph colorings using no extra colors

Suppose the graph G can be r-colored using colors 1,2,...,r, so that no vertex is adjacent to two vertices colored r. If P subset of V(G) is such that the distance between any two vertices in P is at least 12, then any r-coloring of P extends to an r-coloring of all of G. If there exists an r-coloring of G in which the distance between vertices colored r is at least 4 (resp. 6), then any r-coloring of P extends to an r-coloring of all of G provided the distance between any two vertices in P is at least 8 (resp. 6). Similar results hold if P induces a set of cliques. This continues previous work of the authors (Albertson and Moore, J. Combin. Theory Ser. B 77 (1999) 83.) on extending (r + 1)-colorings of r-chromatic graphs. Examples show that the distance constraints on P are almost sharp. We show that triangle-free outerplanar graphs instantiate our results and speculate on other families of graphs that might have r-color extension theorems. (C) 2001 Elsevier Science B.V. All rights reserved.