The s-packing chromatic number of a graph
Discussiones Mathematicae. Graph Theory, Tome 32 (2012) no. 4, pp. 795-806
Voir la notice de l'article provenant de la source Library of Science
Let S = (a₁, a₂, ...) 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.
Keywords:
graph, coloring, packing, broadcast chromatic number
@article{DMGT_2012_32_4_a13,
author = {Goddard, Wayne and Xu, Honghai},
title = {The s-packing chromatic number of a graph},
journal = {Discussiones Mathematicae. Graph Theory},
pages = {795--806},
publisher = {mathdoc},
volume = {32},
number = {4},
year = {2012},
language = {en},
url = {http://geodesic.mathdoc.fr/item/DMGT_2012_32_4_a13/}
}
Goddard, Wayne; Xu, Honghai. The s-packing chromatic number of a graph. Discussiones Mathematicae. Graph Theory, Tome 32 (2012) no. 4, pp. 795-806. http://geodesic.mathdoc.fr/item/DMGT_2012_32_4_a13/