Precoloring Extension for 2‐connected Graphs
Margit Voigt · SIAM Journal on Discrete Mathematics · 2007
Let $G=G(V,E)$ be a simple graph, ℒ a list assignment with $|L(v)|=\Delta(G)$ for all $v\in V$, and $W \subseteq V$ an independent subset of the vertex set. Define $d(W):= {\rm min} \{ d(v,w) | v,w \in W \}$ to be the minimum distance between two vertices of W. In this paper it is shown that if G is 2‐connected with $\Delta(G) \geq 4$ and G is not the complete graph $K_{\Delta(G)+1}$, then every precoloring of W is extendable to a proper list coloring of G provided that $d(W)\geq 4$. An example shows that the bound is sharp. This extends a result of Axenovich [Electron. J. Combin., 10 (2003), note 1] and Albertson, Kostochka, and West [SIAM J. Discrete Math., 18 (2004), pp. 542–553], who proved that $d(W)\geq 8$ guarantees such an extension for all G with $\Delta(G)\geq 3$ not containing $K_{\Delta(G)+1}$.