Packing colourings of claw-free subcubic graphs

arXiv:2610.33803 · math.CO · Submitted 2026-10-24 · Read on arXiv

math.CO

Submitted: 2026-10-24

Updated: 2026-10-24

Comments: 13 pages, 2 figures

License: http://creativecommons.org/licenses/by/4.0/

The gist: We prove that every claw-free subcubic graph admits a-packing colouring, confirming a conjecture of Mortada, El Zein and Al Hajjar.

Abstract

We prove that every claw-free subcubic graph admits a-packing colouring, confirming a conjecture of Mortada, El Zein and Al Hajjar. The proof combines a reduction to line graphs of subdivided loopless cubic multigraphs with local colouring extensions. We also give a negative answer to their question on-packing colourings by constructing an infinite family of connected bridgeless claw-free cubic counterexamples. The smallest graph in this family has 36 vertices. More generally, we characterise the simple cubic graphs whose triangle expansions admit a-packing colouring in terms of gated independent odd-cycle transversals. This characterisation gives a classification for connected bridgeless claw-free cubic bases and shows that the double triangle expansion of a loopless cubic multigraph admits such a colouring if and only if the multigraph has a perfect matching.

Related papers