Geodesic
A Survey on Packing Colorings
Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 4, pp. 923-970

Voir la notice de l'article provenant de la source Library of Science

If S = (a1, a2, . . .) 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 X1, X2, . . . such that for each pair of distinct vertices in the set Xi, the distance between them is larger than ai. If there exists an integer k such that V (G) = X1 ∪ ∪ Xk, 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 ai = 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 its generalization, the S-packing coloring. We also list several conjectures and open problems.
Keywords: packing coloring, packing chromatic number, subcubic graph, S -packing chromatic number, computational complexity 
@article{DMGT_2020_40_4_a0,
     author = {Bre\v{s}ar, Bo\v{s}tjan and Ferme, Jasmina and Klav\v{z}ar, Sandi and Rall, Douglas F.},
     title = {A {Survey} on {Packing} {Colorings}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {923--970},
     publisher = {mathdoc},
     volume = {40},
     number = {4},
     year = {2020},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2020_40_4_a0/}
}
TY  - JOUR
AU  - Brešar, Boštjan
AU  - Ferme, Jasmina
AU  - Klavžar, Sandi
AU  - Rall, Douglas F.
TI  - A Survey on Packing Colorings
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2020
SP  - 923
EP  - 970
VL  - 40
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2020_40_4_a0/
LA  - en
ID  - DMGT_2020_40_4_a0
ER  - 
%0 Journal Article
%A Brešar, Boštjan
%A Ferme, Jasmina
%A Klavžar, Sandi
%A Rall, Douglas F.
%T A Survey on Packing Colorings
%J Discussiones Mathematicae. Graph Theory
%D 2020
%P 923-970
%V 40
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2020_40_4_a0/
%G en
%F DMGT_2020_40_4_a0
Brešar, Boštjan; Ferme, Jasmina; Klavžar, Sandi; Rall, Douglas F. A Survey on Packing Colorings. Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 4, pp. 923-970. http://geodesic.mathdoc.fr/item/DMGT_2020_40_4_a0/