A Note on Graph Coloring Extensions and List-Colorings - Axenovich, Maria (The Electronic Journal of Combinatorics, 2003)
Let G be a graph with maximum degree Δ ≥ 3 not equal to K_Δ +1 and let P be a subset of vertices with pairwise distance, d(P), between them at least 8. Let each vertex x be assigned a list of colors of size Δ if xVP and 1 if xP. We prove that it is possible to color V(G) such that adjacent vertices receive different colors and each vertex has a color from its list. We show that d(P) cannot be improved. This generalization of Brooks’ theorem answers the following question of Albertson positively: If G and P are objects described above, can any coloring of P in at most Δ colors be extended to a proper coloring of G in at most Δ colors?