{"id":"arxiv/2609.20204","url":"https://arxiv.org/abs/2609.20204","tags":["math.CO"],"score":0,"title":"Two-distance and list-two-distance coloring of cacti: the subcubic case and the C5 obstruction","domain":"math.CO","source":"arxiv","authors":["Vaibhav Suvagiya"],"reviews":0,"subject":"math.CO","summary":"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 $\\mathrm{ch}(G^2)$ exactly: they are always equal, and the common value is $Δ+1$ if $Δ\\ge4$, 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 $Δ\\le2$. For $Δ\\ge6$ the value $Δ+1$ is already known, since cacti are outerplanar and hence $K_{2,3}$-minor-free…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-07-25","reactions":{}}