Precoloring Extensions of Brooks' Theorem
Michael O. Albertson, Alexandr V. Kostochka, Douglas B. West · SIAM Journal on Discrete Mathematics · 2004
Let G be a connected graph with maximum degree k (other than a complete graph or odd cycle), let W be a precolored set of vertices in G inducing a subgraph F, and let D be the minimum distance in G between components of F. If the components of F are complete graphs and $D\ge 8$ (for $k\ge 4$) or $D\ge 10$ (for k = 3), then every proper k-coloring of F extends to a proper k-coloring of G. If the components of F are single vertices and $Dge 8$, and the vertices outside W are assigned color lists of size k, then every k-coloring of F extends to a proper coloring of G with the color on each vertex chosen from its list. These results are sharp.