# The s-packing chromatic number of a graph

Discussiones Mathematicae Graph Theory (2012)

- Volume: 32, Issue: 4, page 795-806
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topWayne Goddard, and Honghai Xu. "The s-packing chromatic number of a graph." Discussiones Mathematicae Graph Theory 32.4 (2012): 795-806. <http://eudml.org/doc/270786>.

@article{WayneGoddard2012,

abstract = {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$.},

author = {Wayne Goddard, Honghai Xu},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {graph; coloring; packing; broadcast chromatic number},

language = {eng},

number = {4},

pages = {795-806},

title = {The s-packing chromatic number of a graph},

url = {http://eudml.org/doc/270786},

volume = {32},

year = {2012},

}

TY - JOUR

AU - Wayne Goddard

AU - Honghai Xu

TI - The s-packing chromatic number of a graph

JO - Discussiones Mathematicae Graph Theory

PY - 2012

VL - 32

IS - 4

SP - 795

EP - 806

AB - 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$.

LA - eng

KW - graph; coloring; packing; broadcast chromatic number

UR - http://eudml.org/doc/270786

ER -

## References

top- [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. Zbl1126.05045
- [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. Zbl1219.05185
- [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. Zbl1207.05165
- [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). Zbl0411.68039
- [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. Zbl1224.05172
- [7] C. Sloper, An eccentric coloring of trees, Australas. J. Combin. 29 (2004) 309-321. Zbl1058.05026
- [8] R. Soukal and P. Holub, A note on packing chromatic number of the square lattice, Electron. J. Combin. 17 (2010) Note 17, 7. Zbl1215.05050
- [9] D.B. West, Introduction to Graph Theory (Prentice Hall, NJ, USA, 2001).

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.