PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
Czasopismo
2013 | 11 | 7 | 1344-1357
Tytuł artykułu

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

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
Wydawca
Czasopismo
Rocznik
Tom
11
Numer
7
Strony
1344-1357
Opis fizyczny
Daty
wydano
2013-07-01
online
2013-04-26
Twórcy
  • Department of Mathematics, University of Johannesburg, Auckland Park, 2006, South Africa, yjacobs@uj.ac.za
  • Department of Mathematics, University of Johannesburg, Auckland Park, 2006, South Africa, ejonck@uj.ac.za
  • Department of Mathematics, University of Johannesburg, Auckland Park, 2006, South Africa, ejoubert@uj.ac.za
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
Identyfikator YADDA
bwmeta1.element.doi-10_2478_s11533-013-0237-5
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.