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

Abstract

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.

Keywords

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;

Data

Language: English
Year of publishing:
Typology: 1.01 - Original Scientific Article
Organization: UM FNM - Faculty of Natural Sciences and Mathematics
UDC: 519.17
COBISS: 14418009 Link will open in a new window
ISSN: 0166-218X
Views: 809
Downloads: 90
Average score: 0 (0 votes)
Metadata: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Other data

Secondary language: Unknown
Secondary title: O pakirnem kromatičnem številu kartezičnih produktov, šestkotniške mreže in drevesa
Secondary abstract: 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.
Secondary keywords: 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:
Type (COBISS): Not categorized
Pages: str. 2003-2311
Volume: ǂVol. ǂ155
Issue: ǂiss. ǂ17
Chronology: 2007
ID: 1473191