20.500.12556/DKUM-51602 On the packing chromatic number of Cartesian products, hexagonal lattice, and trees O pakirnem kromatičnem številu kartezičnih produktov, šestkotniške mreže in drevesa Pakirno 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. The packing chromatic number ▫$chi_rho(G)$▫ of a graph ▫$G$▫ is the smallest integer ▫$k$▫ such that the vertex set of ▫$G$▫ can be partitioned into packings with pairwise different widths. Several lower and upper bounds are obtained for the packing chromatic number of Cartesian products of graphs. It is proved that the packing chromatic number of the infinite hexagonal lattice lies between 6 and 8. Optimal lower and upper bounds are proved for subdivision graphs. Trees are also considered and monotone colorings are introduced. matematika teorija grafov pakirno kromatično število kartezični produkt grafov šestkotniška mreža subdividiran graf drevo računska zahtevnost mathematics graph theory packing chromatic number Cartesian product of graphs hexagonal lattice subdivision graph tree computational complexity true false false Angleški jezik Neznan jezik Delo ni kategorizirano 2015-07-10 14:58:52 2015-07-10 14:58:52 2022-05-30 03:06:34 2019-07-11 07:23:26 2007 0 0 str. 2003-2311 iss. 17 Vol. 155 2007 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.17 25342464 14418009 0166-218X URN:SI:UM:DK:WWFHJIXC http://dx.doi.org/10.1016/j.dam.2007.06.008 1 https://dk.um.si/Dokument.php?lang=slv&id=76162 Fakulteta za elektrotehniko, računalništvo in informatiko 0 0 0