Packing colourings of claw-free subcubic graphs
Federico Romaniello
Source abstract
We prove that every claw-free subcubic graph admits a \packA-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 \packB-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 \packB-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.
Evidence graph
No public relationships recorded yet.
Integrity note: This page is a factual metadata record created by deterministic ingestion. It is not a claim that the work moves a mathematical frontier or has been independently verified.