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 L a list assignment to V(G) such that |L(v)| = Δ for all v V(G). Given a set P V(G) of pairwise distance at least d then Albertson, Kostochka and West (2004) and Axenovich (2003) have shown that every L-precolouring of P extends to a 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.