A lower bound for the packing chromatic number of the Cartesian product of cycles

Yolandé Jacobs; Elizabeth Jonck; Ernst Joubert

Open Mathematics (2013)

  • Volume: 11, Issue: 7, page 1344-1357
  • ISSN: 2391-5455

Abstract

top
Let G = (V, E) be a simple graph of order n and i be an integer with i ≥ 1. The set X i ⊆ V(G) is called an i-packing if each two distinct vertices in X i are more than i apart. A packing colouring of G is a partition X = {X 1, X 2, …, X k} of V(G) such that each colour class X i is an i-packing. The minimum order k of a packing colouring is called the packing chromatic number of G, denoted by χρ(G). In this paper we show, using a theoretical proof, that if q = 4t, for some integer t ≥ 3, then 9 ≤ χρ(C 4 □ C q). We will also show that if t is a multiple of four, then χρ(C 4 □ C q) = 9.

How to cite

top

Yolandé Jacobs, Elizabeth Jonck, and Ernst Joubert. "A lower bound for the packing chromatic number of the Cartesian product of cycles." Open Mathematics 11.7 (2013): 1344-1357. <http://eudml.org/doc/269036>.

@article{YolandéJacobs2013,
abstract = {Let G = (V, E) be a simple graph of order n and i be an integer with i ≥ 1. The set X i ⊆ V(G) is called an i-packing if each two distinct vertices in X i are more than i apart. A packing colouring of G is a partition X = \{X 1, X 2, …, X k\} of V(G) such that each colour class X i is an i-packing. The minimum order k of a packing colouring is called the packing chromatic number of G, denoted by χρ(G). In this paper we show, using a theoretical proof, that if q = 4t, for some integer t ≥ 3, then 9 ≤ χρ(C 4 □ C q). We will also show that if t is a multiple of four, then χρ(C 4 □ C q) = 9.},
author = {Yolandé Jacobs, Elizabeth Jonck, Ernst Joubert},
journal = {Open Mathematics},
keywords = {Graph; Packing; Chromatic; Cartesian product; Cycles; Bounds; packing; chromatic; cycles; bounds},
language = {eng},
number = {7},
pages = {1344-1357},
title = {A lower bound for the packing chromatic number of the Cartesian product of cycles},
url = {http://eudml.org/doc/269036},
volume = {11},
year = {2013},
}

TY - JOUR
AU - Yolandé Jacobs
AU - Elizabeth Jonck
AU - Ernst Joubert
TI - A lower bound for the packing chromatic number of the Cartesian product of cycles
JO - Open Mathematics
PY - 2013
VL - 11
IS - 7
SP - 1344
EP - 1357
AB - Let G = (V, E) be a simple graph of order n and i be an integer with i ≥ 1. The set X i ⊆ V(G) is called an i-packing if each two distinct vertices in X i are more than i apart. A packing colouring of G is a partition X = {X 1, X 2, …, X k} of V(G) such that each colour class X i is an i-packing. The minimum order k of a packing colouring is called the packing chromatic number of G, denoted by χρ(G). In this paper we show, using a theoretical proof, that if q = 4t, for some integer t ≥ 3, then 9 ≤ χρ(C 4 □ C q). We will also show that if t is a multiple of four, then χρ(C 4 □ C q) = 9.
LA - eng
KW - Graph; Packing; Chromatic; Cartesian product; Cycles; Bounds; packing; chromatic; cycles; bounds
UR - http://eudml.org/doc/269036
ER -

References

top
  1. [1] Brešar B., Klavžar S., Rall D.F., On the packing chromatic number of Cartesian products, hexagonal lattice, and trees, Discrete Appl. Math., 2007, 155(17), 2303–2311 http://dx.doi.org/10.1016/j.dam.2007.06.008[Crossref][WoS] Zbl1126.05045
  2. [2] Chartrand G., Lesniak L., Zhang P., Graphs & Digraphs, 5th ed., CRC Press, Boca Raton, 2011 
  3. [3] Ekstein J., Fiala J., Holub P., Lidický B., The packing chromatic number of the square lattice is at least 12, available at http://arxiv.org/abs/1003.2291 
  4. [4] Fiala J., Golovach P.A., Complexity of the packing coloring problem for trees, Discrete Appl. Math., 2010, 158(7), 771–778 http://dx.doi.org/10.1016/j.dam.2008.09.001[Crossref][WoS] Zbl1219.05185
  5. [5] Fiala J., Klavžar S., Lidický B., The packing chromatic number of infinite product graphs, European J. Combin., 2009, 30(5), 1101–1113 http://dx.doi.org/10.1016/j.ejc.2008.09.014[Crossref][WoS] Zbl1207.05165
  6. [6] Finbow A.S., Rall D.F., On the packing chromatic number of some lattices, Discrete Appl. Math., 2010, 158(12), 1224–1228 http://dx.doi.org/10.1016/j.dam.2009.06.001[WoS][Crossref] Zbl1221.05137
  7. [7] Goddard W., Hedetniemi S.M., Hedetniemi S.T., Harris J.M., Rall D.F., Broadcast chromatic numbers of graphs, Ars Combin., 2008, 86, 33–49 Zbl1224.05172
  8. [8] Sloper C., Broadcast-coloring in trees, Reports in Informatics, #233, University of Bergen, Bergen, 2002, available at http://www.ii.uib.no/~sloper/Papers/brep.pdf 
  9. [9] Soukal R., Holub P., A note on packing chromatic number of the square lattice, Electron. J. Combin., 2010, 17, #17 Zbl1215.05050

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.