Extending Colorings

It is easy to construct a graph G with chromatic number r and an(r+1)-coloring of a subgraph H whose vertices are all of distance 2 far apart so that an extension of the coloring to G requires r new colors.A theorem of Albertson and Moore states that if the distance between any two vertices in H is at least 3,then an(r+1)-coloring of H extends to a coloring of G using no more than[(3r+1)/2]colors.Generalizing a theorem of Albertson,Kostochka showed that if H comprises cliques of order k whose pairwise distance is at least 4k,then an(r+1)-coloring of H extends to an(r+1)-coloring of G.Generalizing their results,we show that if H comprises cliques of order k with pairwise distance at least 3,then an s-coloring of H extends to a coloring of G using no more than r+s-[s/min {r,k+1}]colors for s?k and the bound on the number of colors is sharp.Another theorem of Albertson and Moore relates the structure of the precolored components to the number of extra colors needed in the extension.We construct graphs to show that their result is sharp if the number of vertices in a component is close to its chromatic number and also improve it by giving sharp color extension in other cases.