A Note on Graph Coloring Extensions and List-Colorings

Abstract

Let $G$ be a graph with maximum degree $\Delta \geq 3$ not equal to $K_{\Delta +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 $\Delta$ if $x\in V\setminus P$ and $1$ if $x\in P$. 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 $\Delta$ colors be extended to a proper coloring of $G$ in at most $\Delta$ colors?