On the packing chromatic number of Cartesian products, hexagonal lattice, and treesBrešar, Boštjan (Avtor) Klavžar, Sandi (Avtor) Rall, Douglas F. (Avtor) matematikateorija grafovpakirno kromatično številokartezični produkt grafovšestkotniška mrežasubdividiran grafdrevoračunska zahtevnostmathematicsgraph theorypacking chromatic numberCartesian product of graphshexagonal latticesubdivision graphtreecomputational complexityPakirno kromatično število ▫$chi_{rho}(G)$▫ grafa ▫$G$▫ je najmanjše število ▫$k$▫, tako da lahko množico vozlišč grafa ▫$G$▫ razbijemo v pakiranja s paroma različnimi širinami. Dobljenih je več spodnjih in zgornjih meja za pakirno kromatično število kartezičnega produkta grafov. Dokazano je, da pakirno kromatično število šestkotniške mreže leži med 6 in 8. Optimalne spodnje in zgornje meje so dokazane za subdividirane grafe. Obravnavana so tudi drevesa ter vpeljana monotona barvanja.20072015-07-10 14:58:52Delo ni kategorizirano51602UDK: 519.17OceCobissID: 25342464COBISS_ID: 14418009ISSN pri članku: 0166-218XNUK URN: URN:SI:UM:DK:WWFHJIXCsl