PL EN

Preferencje
Język
Widoczny [Schowaj] Abstrakt
Liczba wyników
Czasopismo

## Open Mathematics

2013 | 11 | 7 | 1344-1357
Tytuł artykułu

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

Autorzy
Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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.
Słowa kluczowe
EN
Kategorie tematyczne
Wydawca
Czasopismo
Rocznik
Tom
Numer
Strony
1344-1357
Opis fizyczny
Daty
wydano
2013-07-01
online
2013-04-26
Twórcy
autor
• Department of Mathematics, University of Johannesburg, Auckland Park, 2006, South Africa
autor
• Department of Mathematics, University of Johannesburg, Auckland Park, 2006, South Africa
autor
• Department of Mathematics, University of Johannesburg, Auckland Park, 2006, South Africa
Bibliografia
• [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]
• [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]
• [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]
• [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]
• [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
• [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
Typ dokumentu
Bibliografia
Identyfikatory