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.
@article{bwmeta1.element.doi-10_2478_s11533-013-0237-5,
author = {Yoland\'e Jacobs and Elizabeth Jonck and Ernst Joubert},
title = {A lower bound for the packing chromatic number of the Cartesian product of cycles},
journal = {Open Mathematics},
volume = {11},
year = {2013},
pages = {1344-1357},
zbl = {1266.05121},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_2478_s11533-013-0237-5}
}
Yolandé Jacobs; Elizabeth Jonck; Ernst Joubert. A lower bound for the packing chromatic number of the Cartesian product of cycles. Open Mathematics, Tome 11 (2013) pp. 1344-1357. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_2478_s11533-013-0237-5/
[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] | Zbl 1126.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] | Zbl 1219.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] | Zbl 1207.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] | Zbl 1221.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 | Zbl 1224.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 | Zbl 1215.05050