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

Povzetek

Če je ▫$S=(a_1,a_2,\ldots)$▫ nepadajoče zaporedje naravnih števil, potem je ▫$S$▫-pakirno barvanje grafa ▫$G$▫ taka particija množice vozlišč ▫$V(G)$▫ na množice ▫$X_1,X_2, \ldots$▫, da je razdalja med vsakima različnima vozliščema poljubne množice ▫$X_i$▫ večja kot ▫$a_i$▫. Če obstaja tako število ▫$k$▫, da je ▫$V(G)=X_1\cup \cdots \cup X_k$▫, potem particijo imenujemo ▫$S$▫-pakirno ▫$k$▫-barvanje. Najmanjše tako število ▫$k$▫, da ▫$G$▫ premore ▫$S$▫-pakirno ▫$k$▫-barvanje imenujemo ▫$S$▫-pakirno kromatično število grafa ▫$G$▫. Če je ▫$a_i=i$▫ za vsa naravna števila ▫$i$▫, potem se izraza poenostavita v pakirno barvanje in pakirno kromatično število. Od vpeljave teh posplošitev kromatičnega števila v letu 2008 je bilo objavljenih preko 50 člankov na to temo. V tem članku naredimo pregled stanja na področju pakirnih barvanj in njihovih posplošitev ▫$S$▫-pakirnih barvanj. Predstavimo tudi več odprtih problemov in domnev.

Ključne besede

pakirno barvanje;pakirno kromatično število;podkubični graf;S-pakirno kromatično število;računska zahtevnost;packing coloring;packing chromatic number;subcubic graph;S-packing chromatic number;computational complexity;

Podatki

Jezik: Angleški jezik
Leto izida:
Tipologija: 1.02 - Pregledni znanstveni članek
Organizacija: UL FMF - Fakulteta za matematiko in fiziko
Založnik: Technical University Press
UDK: 519.17
COBISS: 23220483 Povezava se bo odprla v novem oknu
ISSN: 1234-3099
Št. ogledov: 0
Št. prenosov: 0
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: Slovenski jezik
Sekundarni naslov: Pregledni članek o pakirnih barvanjih
Sekundarni povzetek: If ▫$S=(a_1,a_2,\ldots)$▫ is a non-decreasing sequence of positive integers, then an ▫$S$▫-packing coloring of a graph ▫$G$▫ is a partition of ▫$V (G)$▫ into sets ▫$X_1,X_2, \ldots$▫ such that for each pair of distinct vertices in the set ▫$X_i$▫, the distance between them is larger than ▫$a_i$▫. If there exists an integer ▫$k$▫ such that ▫$V(G)=X_1\cup \cdots \cup X_k$▫, then the partition is called an ▫$S$▫-packing ▫$k$▫-coloring. The ▫$S$▫-packing chromatic number of ▫$G$▫ is the smallest ▫$k$▫ such that ▫$G$▫ admits an ▫$S$▫-packing ▫$k$▫-coloring. If ▫$a_i=i$▫ for every ▫$i$▫, then the terminology reduces to packing colorings and packing chromatic number. Since the introduction of these generalizations of the chromatic number in 2008 more than fifty papers followed. Here we survey the state of the art on the packing coloring, and ts generalization, the ▫$S$▫-packing coloring. We also list several conjecres and open problems.
Sekundarne ključne besede: pakirno barvanje;pakirno kromatično število;podkubični graf;S-pakirno kromatično število;računska zahtevnost;
Vrsta dela (COBISS): Znanstveno delo
Strani: str. 923-970
Letnik: ǂVol. ǂ40
Zvezek: ǂno. ǂ4
Čas izdaje: 2020
DOI: 10.7151/dmgt.2320
ID: 26043972