2025/03/24 by Mortada, Maidoun, Togni, Olivier
#05C15 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2503.18793
Given a sequence S=(s1,s2,…,sp), p≥ 2, of non-decreasing integers, an S-packing coloring of a graph G is a partition of its vertex set into p disjoint sets V1,…, Vp such that any two distinct vertices of Vi are at a distance greater than si, 1≤ i≤ p. In this paper, we study the S-packing coloring problem on graphs of bounded maximum degree and for sequences mainly containing 1's and 2's (ir in a sequence means i is repeated r times). Generalizing existing results for subcubic graphs, we prove a series of results on graphs of maximum degree k: We show that graphs of maximum degree k are (1k-1,2k)-packing colorable. Moreover, we refine this result for restricted subclasses: A graph of maximum degree k is said to be t-saturated, 0≤ t≤ k, if every vertex of degree k is adjacent to at most t vertices of degree k. We prove that any graph of maximum degree k≥ 3 is (1k-1, 3)-packing colorable if it is 0-saturated, (1k-1, 2)-packing colorable if it is t-saturated, 1≤ t≤ k-2; and (1k-1,2k-1)-packing colorable if it is (k-1)-saturated. We also propose some conjectures and questions.