Packing colourings of claw-free subcubic graphs
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
- Three-ends Furstenberg estimates and approximate rectangles
- Multicolor Ramsey numbers of ordered matchings
- Exponential random graph models with soft clique constraints
- A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
- Ehrhart positivity for paving positroids
- Nonlinear lower-tail large deviations at criticality