Two-distance and list-two-distance coloring of cacti: the subcubic case and the C5 obstruction
Abstract
The square G2 of a graph joins two vertices at distance at most two; a proper coloring of G2 is a 2-distance coloring of G. For a cactus G (every edge on at most one cycle) we determine both the 2-distance chromatic number χ(G2) and the choice number ch(G2) exactly: they are always equal, and the common value is Δ+1 if Δ≥4, is 4 if Δ=3 and G has no block equal to C5, is 5 if Δ=3 and G has a C5 block, and is the classical value if Δ≤2. For Δ≥6 the value Δ+1 is already known, since cacti are outerplanar and hence K2,3-minor-free (Hetherington-Woodall; Agnarsson-Halldorsson). Our contribution is the small-degree regime. For subcubic cacti we obtain a complete classification in both the ordinary and list settings, with the 5-cycle as the unique obstruction; the list statement has no prior analogue and is a genuine positive instance of the List Square Coloring Conjecture, which is false in general. A single elimination order then handles all Δ≥4 uniformly and, in particular, settles the two cases Δ∈{4,5} that the superclass bounds leave at Δ+2. The number 5 turns out to be one obstruction wearing three disguises: C52=K5, the Frobenius number of {3,4}, and a degenerate K4 list-coloring instance.
Related
- On (1,24) and (1,25)-packing edge-coloring of sparse subcubic graphs
- List 3-Coloring in tame classes of graphs in quasipolynomial time
- List coloring C3-free planar graphs with a sparse matching of restricted lists
- Sufficiency of Hall's Condition for Graphic List Coloring
- The List Edge-Coloring Conjecture for New Infinite Families
BibTeX
@misc{suvagiya2026twodistance,
title = {{Two-distance and list-two-distance coloring of cacti: the subcubic case and the C5 obstruction}},
author = {Vaibhav Suvagiya},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.20204},
eprint = {2609.20204},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.20204},
}
RIS
TY - UNPB
TI - Two-distance and list-two-distance coloring of cacti: the subcubic case and the C5 obstruction
AU - Vaibhav Suvagiya
PY - 2026
DA - 2026/09/01
PB - arXiv
DO - 10.48550/arxiv.2609.20204
UR - https://arxiv.org/abs/2609.20204
AB - The square G^2 of a graph joins two vertices at distance at most two; a proper coloring of G^2 is a 2-distance coloring of G. For a cactus G (every edge on at most one cycle) we determine both the 2-distance chromatic number χ(G^2) and the choice number ch(G^2) exactly: they are always equal, and the common value is Δ+1 if Δ≥4, is 4 if Δ=3 and G has no block equal to C_5, is 5 if Δ=3 and G has a C_5 block, and is the classical value if Δ≤2. For Δ≥6 the value Δ+1 is already known, since cacti are outerplanar and hence K_2,3-minor-free (Hetherington-Woodall; Agnarsson-Halldorsson). Our contribution is the small-degree regime. For subcubic cacti we obtain a complete classification in both the ordinary and list settings, with the 5-cycle as the unique obstruction; the list statement has no prior analogue and is a genuine positive instance of the List Square Coloring Conjecture, which is false in general. A single elimination order then handles all Δ≥4 uniformly and, in particular, settles the two cases Δ∈{4,5} that the superclass bounds leave at Δ+2. The number 5 turns out to be one obstruction wearing three disguises: C_5^2=K_5, the Frobenius number of {3,4}, and a degenerate K_4 list-coloring instance.
ER -