Advances on the Packing Coloring Conjectures of Subcubic Graphs

Abstract

For a non-decreasing sequence of integers $S=(s_1,s_2,\dots ,s_k)$, an $S$-packing coloring of $G$ is a partition of $V(G)$ into $k$ subsets $V_1,V_2,\dots ,V_k$ such that the distance between any two distinct vertices $x,y\in V_i$ is at least $s_i+1$, $1\le i\le k$. The packing chromatic number $\ddot{I}{‡}_{\ddot{I}}(G)$ of a graph $G$ is the smallest integer $p$ such that $G$ is $(1,2,\dots ,p)$-packing colorable. Gastineau and Togni asked whether the subdivision $S(G)$ of every subcubic graph $G$ has $\ddot{I}{‡}_{\ddot{I}}(S(G))\le 5$ and whether every subcubic graph, except the Petersen graph, is $(1,1,2,2)$-packing colorable; these questions were later conjectured by BreÅ¡ar et al. Moreover, Gastineau and Togni proved that a positive answer to the second question implies a positive answer to the first. In this paper, we completely resolve the second question for connected non-regular subcubic graphs, proving that they are $(1,1,2,2)$-packing colorable and hence satisfy $\ddot{I}{‡}_{\ddot{I}}(S(G))\le 5$. We also establish the same result for several classes of cubic graphs, including those with diamonds, certain cut-vertices, and bridges on short cycles. Finally, we strengthen the recent result of Liu, Zhang, and Zhang [\textit{Discrete Math.} 348 (11) (2025). 114610] that every subcubic graph is $(1,1,2,2,3)$-packing colorable by proving that every connected cubic graph admits a $(1,1,2,2,k)$-packing coloring in which at most one vertex receives color $k$, where $k$ is arbitrary. This not only simplifies the existing argument but also strictly improves the bound.