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 , and the S-packing chromatic number 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 and determine for several common families of graphs. We examine for the infinite path and give some exact values and asymptotic bounds. Finally we consider complexity questions, especially about recognizing graphs with .
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1642,
author = {Wayne Goddard and Honghai Xu},
title = {The s-packing chromatic number of a graph},
journal = {Discussiones Mathematicae Graph Theory},
volume = {32},
year = {2012},
pages = {795-806},
zbl = {1293.05106},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1642}
}
Wayne Goddard; Honghai Xu. The s-packing chromatic number of a graph. Discussiones Mathematicae Graph Theory, Tome 32 (2012) pp. 795-806. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1642/
[000] [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. | Zbl 1126.05045
[001] [2] J. Ekstein, J.Fiala, P.Holub and B. Lidický, The packing chromatic number of the square lattice is at least 12, preprint.
[002] [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. | Zbl 1219.05185
[003] [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. | Zbl 1207.05165
[004] [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). | Zbl 0411.68039
[005] [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. | Zbl 1224.05172
[006] [7] C. Sloper, An eccentric coloring of trees, Australas. J. Combin. 29 (2004) 309-321. | Zbl 1058.05026
[007] [8] R. Soukal and P. Holub, A note on packing chromatic number of the square lattice, Electron. J. Combin. 17 (2010) Note 17, 7. | Zbl 1215.05050
[008] [9] D.B. West, Introduction to Graph Theory (Prentice Hall, NJ, USA, 2001).