Every subcubic graph is packing (1,1,2,2,3)-colorable
Xujun Liu, Xin Zhang, Yan-ting Yann Zhang · Discrete Mathematics · 2025
For a sequence S = ( s 1 , … , 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 , … , V k such that for every pair of distinct vertices u , v ∈ V i , where 1 ≤ i ≤ k , the distance between u and v is at least s i + 1 . The packing chromatic number, χ p ( G ) , of a graph G is the smallest integer k such that G has a packing ( 1 , 2 , … , 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, χ p ( D ( G ) ) ≤ 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.