Impact of local girth on the S-packing coloring of k-saturated subcubic graphs

Abstract

For a non-decreasing sequence $S=(s_1,s_2,\dots ,s_k)$, an $S$-packing coloring of a graph $G$ is a vertex coloring using the colors $s_1,s_2,\dots ,s_k$ such that any two vertices assigned the same color $s_i$ are at distance greater than $s_i$. A subcubic graph is said to be $k$-saturated, for $0\le k\le 3$, if every vertex of degree 3 is adjacent to at most $k$ vertices of degree~3. The \emph{local girth} of a vertex is the length of the smallest cycle containing it. Brešar, Kuenzel, and Rall [\textit{Discrete Math.} 348(8) (2025),~114477] proved that every claw-free cubic graph is $(1,1,2,2)$-packing colorable, confirming the conjecture for this family. Equivalently, a claw-free cubic graph is one in which each $3$-vertex has local girth~3. Motivated by this observation and by recent progress on $S$-packing colorings of $k$-saturated subcubic graphs, we study the influence of local girth on their $S$-packing colorability. We establish a series of results describing how the parameters of saturation and local girth jointly determine the admissible $S$-packing sequences. Sharpness is verified through explicit constructions, and several open problems are posed to delineate the remaining cases.