A note on \(K^-_{\Delta +1}\)-free precolouring with \(\Delta\) colours (Q2380218)

Summary: Let \(G\) be a simple graph of maximum degree \(\Delta\geq 3\), not containing \(K_{\Delta+1}\), and \({\mathcal L}\) a list assignment to \(V(G)\) such that \(|{\mathcal L}(v)|= \Delta\) for all \(v\in V(G)\). Given a set \(P\subset V(G)\) of pairwise distance at least \(d\) then \textit{M. O. Albertson, A. V. Kostochka} and \textit{D. B. West} [SIAM J. Discrete Math. 18, No.~3, 542--553 (2005; Zbl 1069.05031)] and \textit{M. Axenovich} [Electron. J. Comb. 10, Research paper N1, 5 p. (2003); printed version J. Comb. 10, No.~1 (2003; Zbl 1017.05041)] have shown that every \({\mathcal L}\)-precolouring of \(P\) extends to a \({\mathcal L}\)-colouring of \(G\) provided \(d\geq 8\). Let \(K_{\Delta+1}^-\) denote the graph \(K_{\Delta+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_{\Delta+1}^-\) or \(K_\Delta\) 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 \textit{M. Voigt} [SIAM J. Discrete Math. 21, No.~1, 258--263 (2007; Zbl 1139.05320); Discrete Math. 309, No.~15, 4926--4930 (2009; Zbl 1209.05102)] for which counterexamples are given.