Geodesic
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/}
}
TY  - JOUR
AU  - Goddard, Wayne
AU  - Xu, Honghai
TI  - The s-packing chromatic number of a graph
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2012
SP  - 795
EP  - 806
VL  - 32
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2012_32_4_a13/
LA  - en
ID  - DMGT_2012_32_4_a13
ER  - 
%0 Journal Article
%A Goddard, Wayne
%A Xu, Honghai
%T The s-packing chromatic number of a graph
%J Discussiones Mathematicae. Graph Theory
%D 2012
%P 795-806
%V 32
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2012_32_4_a13/
%G en
%F 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/

[1] B. Brešar and S. Klavžar and D.F. Rall, On the packing chromatic number of Cartesian products, hexagonal lattice, and trees, Discrete Appl. Math. 155 (2007) 2303-2311, doi: 10.1016/j.dam.2007.06.008.

[2] J. Ekstein, J.Fiala, P.Holub and B. Lidický, The packing chromatic number of the square lattice is at least 12, preprint.

[3] J. Fiala and P.A. Golovach, Complexity of the packing coloring problem for trees, Discrete Appl. Math. 158 (2010) 771-778, doi: 10.1016/j.dam.2008.09.001.

[4] J. Fiala, S. Klavžar and B. Lidický, The packing chromatic number of infinite product graphs, European J. Combin. 30 (2009) 1101-1113, doi: 10.1016/j.ejc.2008.09.014.

[5] M.R. Garey and D.S. Johnson, Computers and Intractability, A guide to the Theory of NP-completeness (W. H. Freeman and Co., San Francisco, Calif., 1979).

[6] W. Goddard, S.M. Hedetniemi, S.T. Hedetniemi, J.M. Harris and D.F. Rall, Broadcast chromatic numbers of graphs, Ars Combin. 8 (2008) 33-49.

[7] C. Sloper, An eccentric coloring of trees, Australas. J. Combin. 29 (2004) 309-321.

[8] R. Soukal and P. Holub, A note on packing chromatic number of the square lattice, Electron. J. Combin. 17 (2010) Note 17, 7.

[9] D.B. West, Introduction to Graph Theory (Prentice Hall, NJ, USA, 2001).