Further results and questions on S-packing coloring of subcubic graphs
Maidoun Mortada, Olivier Togni
Abstract
For a non-decreasing sequence of integers S = ( a 1 , a 2 , … , a k ) , an S -packing coloring of G is a partition of V ( G ) into k subsets V 1 , V 2 , … , V k such that the distance between any two distinct vertices x , y ∈ V i is at least a i + 1 , 1 ≤ i ≤ k . We consider the S -packing coloring problem on subclasses of subcubic graphs: For 0 ≤ i ≤ 3 , a subcubic graph G is said to be i -saturated if every vertex of degree 3 is adjacent to at most i vertices of degree 3. Furthermore, a vertex of degree 3 in a subcubic graph is called heavy if all its three neighbors are of degree 3, and G is said to be ( 3 , i ) -saturated if every heavy vertex is adjacent to at most i heavy vertices. We prove that every 1-saturated subcubic graph is ( 1 , 1 , 3 , 3 ) -packing colorable and ( 1 , 2 , 2 , 2 , 2 ) -packing colorable. We also prove that every ( 3 , 0 ) -saturated subcubic graph is ( 1 , 2 , 2 , 2 , 2 , 2 ) -packing colorable.