ALL libraries (COBIB.SI union bibliographic/catalogue database)
  • The packing chromatic number of infinite product graphs
    Fiala, Jiří, 1973- ; Klavžar, Sandi ; Lidický, Bernard
    Pakirno kromatično število ▫$\chi_\rho(G)$▫ grafa ▫$G$▫ je najmanjše število ▫$k$▫, tako da lahko množico vozlišč grafa ▫$G$▫ razbijemo v razrede ▫$X_1,...,X_k$▫, kjer so vozlišča iz ▫$X_i$▫ paroma ... na razdalji večji od ▫$i$▫. Za kartezični produkt poti in dvodimenzionalne kvadratne mreže je dokazano, da za vsak ▫$m\ge 2$▫ velja ▫$\chi_\rho(P_m \square {\mathbb{Z}}^2) = \infty$▫. S tem je razširjen rezultat ▫$\chi_\rho({\mathbb{Z}}^3) = \infty$▫ iz članka [A. Finbow, D. F. Rall, On the packing chromatic number of some lattices, Discrete Appl. Math. (submitted for publication) special issue LAGOS'07]. Dokazano je tudi, da velja ▫$\chi_\rho({\mathbb{Z}}^2) \ge 10$▫, kar izboljša mejo ▫$\chi_\rho({\mathbb{Z}}^2) \ge 9$▫ iz [W. Goddard, S.M.Hedetniemi, S. T. Hedetniemi, J. M. Harris, D. F. Rall, Broadcast chromatic numbers of graphs, Ars Combin. 86 (2008) 33-49]. Nadalje je dokazano, da za vsak končen graf ▫$G$▫ velja ▫$\chi_\rho(G \square{\mathbb{Z}}) < \infty$▫. Obravnavana je tudi neskončna šestkotniška mreža ▫$\mathscr{H}$▫, za katero je dokazano, da velja ▫$\chi_\rho({\mathscr{H}}) \le 7$▫ in ▫$\chi_\rho(P_m \square{\mathscr{H}}) = \infty$▫ for ▫$m \ge 6$▫.
    Source: European journal of combinatorics = Journal européen de combinatoire = Europäische Zeitschrift für Kombinatorik. - ISSN 0195-6698 (Vol. 30, no. 5, 2009, str. 1101-1113)
    Type of material - article, component part
    Publish date - 2009
    Language - english
    COBISS.SI-ID - 15146585

    Link(s):

    http://dx.doi.org/10.1016/j.ejc.2008.09.014

Shelf entry