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

Tom Rackham

The electronic journal of combinatorics, Tome 16 (2009) no. 1

Résumé

Let $G$ be a simple graph of maximum degree $\Delta \geq 3$, not containing $K_{\Delta + 1}$, and ${\cal L}$ a list assignment to $V(G)$ such that $|{\cal L}(v)| = \Delta$ 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 \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 Voigt (2007, 2008) for which counterexamples are given.

Détail

DOI : 10.37236/266

Classification : 05C15, 05C12, 05C40
Mots-clés : precolouring, pairwise distance, connectivity