Every subcubic graph is packing $(1,1,2,2,3)$-colorable

Abstract

For a sequence $S=(s_1,\dots ,s_k)$ of non-decreasing integers, a packing $S$-coloring of a graph $G$ is a partition of its vertex set $V(G)$ into $V_1,\dots ,V_k$ such that for every pair of distinct vertices $u,v\in V_i$, where $1\le i\le k$, the distance between $u$ and $v$ is at least $s_i+1$. The packing chromatic number, ${\chi }_p(G)$, of a graph $G$ is the smallest integer $k$ such that $G$ has a packing $(1,2,\dots ,k)$-coloring. Gastineau and Togni asked an open question ``Is it true that the $1$-subdivision ($D(G)$) of any subcubic graph $G$ has packing chromatic number at most $5$?'' and later Brešar, Klavžar, Rall, and Wash conjectured that it is true. In this paper, we prove that every subcubic graph has a packing $(1,1,2,2,3)$-coloring and it is sharp due to the existence of subcubic graphs that are not packing $(1,1,2,2)$-colorable. As a corollary of our result, ${\chi }_p(D(G))\le 6$ for every subcubic graph $G$, improving a previous bound ($8$) due to Balogh, Kostochka, and Liu in 2019, and we are now just one step away from fully solving the conjecture.

9 pages, 2 figures