Boštjan Brešar (Avtor), Sandi Klavžar (Avtor), Douglas F. Rall (Avtor)

Povzetek

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.

Ključne besede

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;

Podatki

Jezik: Angleški jezik
Leto izida:
Tipologija: 1.01 - Izvirni znanstveni članek
Organizacija: UM FNM - Fakulteta za naravoslovje in matematiko
UDK: 519.17
COBISS: 14418009 Povezava se bo odprla v novem oknu
ISSN: 0166-218X
Št. ogledov: 809
Št. prenosov: 90
Ocena: 0 (0 glasov)
Metapodatki: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Ostali podatki

Sekundarni jezik: Neznan jezik
Sekundarni naslov: O pakirnem kromatičnem številu kartezičnih produktov, šestkotniške mreže in drevesa
Sekundarni povzetek: 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.
Sekundarne ključne besede: matematika;teorija grafov;pakirno kromatično število;kartezični produkt grafov;šestkotniška mreža;subdividiran graf;drevo;računska zahtevnost;
URN: URN:SI:UM:
Vrsta dela (COBISS): Delo ni kategorizirano
Strani: str. 2003-2311
Letnik: ǂVol. ǂ155
Zvezek: ǂiss. ǂ17
Čas izdaje: 2007
ID: 1473191