# 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

## Access Full Article

top## Abstract

top## How to cite

topYolandé 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] 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] Chartrand G., Lesniak L., Zhang P., Graphs & Digraphs, 5th ed., CRC Press, Boca Raton, 2011
- [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] 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] 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] 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] 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] 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] Soukal R., Holub P., A note on packing chromatic number of the square lattice, Electron. J. Combin., 2010, 17, #17 Zbl1215.05050

## NotesEmbed ?

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