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

Abstract

Č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.

Keywords

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;

Data

Language: English
Year of publishing:
Typology: 1.02 - Review Article
Organization: UL FMF - Faculty of Mathematics and Physics
Publisher: Technical University Press
UDC: 519.17
COBISS: 23220483 Link will open in a new window
ISSN: 1234-3099
Views: 0
Downloads: 0
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: Slovenian
Secondary title: Pregledni članek o pakirnih barvanjih
Secondary abstract: 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.
Secondary keywords: pakirno barvanje;pakirno kromatično število;podkubični graf;S-pakirno kromatično število;računska zahtevnost;
Type (COBISS): Scientific work
Pages: str. 923-970
Volume: ǂVol. ǂ40
Issue: ǂno. ǂ4
Chronology: 2020
DOI: 10.7151/dmgt.2320
ID: 26043972