Discussiones Mathematicae Graph Theory 32(4) (2012) 795-806
doi: 10.7151/dmgt.1642

[BIBTex] [PDF] [PS]

The S-packing Chromatic Number of a Graph

Wayne Goddard and Honghai Xu

Dept of Mathematical Sciences
Clemson University, Clemson SC 29634

Abstract

Let S = (a1, a2, …) 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 ai, 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

2010 Mathematics Subject Classification: 05C15, 05C69.

References

[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).

Received 27 August 2011
Revised 22 February 2012
Accepted 23 February 2012