The S-packing chromatic number of a graph
Wayne Goddard, Honghai Xu · Discussiones Mathematicae Graph Theory · 2012
Let S = (a 1 , a 2 , . ..) be an infinite nondecreasing sequence of positive integers.An S-packing k-coloring of a graph G is a mapping from V (G) to {1, 2, . . ., k} such that vertices with color i have pairwise distance greater than a i , and the S-packing chromatic number χ S (G) of G is the smallest integer k such that G has an S-packing k-coloring.This concept generalizes the concept of proper coloring (when S = (1, 1, 1, . ..)) and broadcast coloring (when S = (1, 2, 3, 4, . ..)).In this paper, we consider bounds on the parameter and its relationship with other parameters.We characterize the graphs with χ S = 2 and determine χ S for several common families of graphs.We examine χ S for the infinite path and give some exact values and asymptotic bounds.Finally we consider complexity questions, especially about recognizing graphs with χ S = 3.