The s-packing chromatic number of a graph

Wayne Goddard; Honghai Xu

Discussiones Mathematicae Graph Theory (2012)

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

Abstract

top
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 .

How to cite

top

Wayne 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. [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. [2] J. Ekstein, J.Fiala, P.Holub and B. Lidický, The packing chromatic number of the square lattice is at least 12, preprint. 
  3. [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. [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. [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. [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. [7] C. Sloper, An eccentric coloring of trees, Australas. J. Combin. 29 (2004) 309-321. Zbl1058.05026
  8. [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. [9] D.B. West, Introduction to Graph Theory (Prentice Hall, NJ, USA, 2001). 

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.