A Note on $K_{Δ+1}^-$-Free Precolouring with $Δ$ Colours - Rackham, Tom (The Electronic Journal of Combinatorics, 2009)
Let $G$ be a simple graph of maximum degree $Δ ≥ 3$, not containing $K_{Δ + 1}$, and ${\cal L}$ a list assignment to $V(G)$ such that $|{\cal L}(v)| = Δ$ for all $v \in V(G)$. Given a set $P \subset V(G)$ of pairwise distance at least $d$ then Albertson, Kostochka and West (2004) and Axenovich (2003) have shown that every ${\cal L}$-precolouring of $P$ extends to a ${\cal L}$-colouring of $G$ provided $d ≥ 8$. Let $K_{Δ + 1}^-$ denote the graph $K_{Δ + 1}$ with one edge removed. In this paper, we consider the problem above and the effect on the pairwise distance required when we additionally forbid either $K_{Δ + 1}^-$ or $K_{Δ}$ as a subgraph of $G$. We have the corollary that an extra assumption of 3-edge-connectivity in the above result is sufficient to reduce this distance from $8$ to $4$. This bound is sharp with respect to both the connectivity and distance. In particular, this corrects the results of Voigt (2007, 2008) for which counterexamples are given.