20.500.12556/DKUM-92011 A survey on packing colorings Pregledni članek o pakirnih barvanjih 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 U ... U 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 ts generalization, the S-packing coloring. We also list several conjecres and open problems. Če je S=(a1,a2,...) nepadajoče zaporedje naravnih števil, potem je S-pakirno barvanje grafa G taka particija množice vozlišč V(G) na množice X1,X2,..., da je razdalja med vsakima različnima vozliščema poljubne množice Xi večja kot ai. Če obstaja tako število k, da je V(G)=X1 U ... U Xk, 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 ai=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. packing coloring packing chromatic number subcubic graph S-packing chromatic number computational complexity pakirno barvanje pakirno kromatično število podkubični graf S-pakirno kromatično število računska zahtevnost true false true Technical University Press Angleški jezik Slovenski jezik Znanstveno delo 2025-03-11 10:03:04 2025-03-11 10:27:21 2025-03-12 03:12:42 0000-00-00 00:00:00 2020 0 0 Str. 923-970 št. 4 Letn. 40 2020 0000-00-00 Zaloznikova Objavljeno NiDoloceno 2020-01-31 2020-04-08 0000-00-00 519.17 23220483 10.7151/dmgt.2320 1234-3099 Bresar-2020-A_SURVEY_ON_PACKING_COLORINGS.pdf Bresar-2020-A_SURVEY_ON_PACKING_COLORINGS.pdf 1 472514A70A4C09C93A3C6E62D459DF5B 78dbb2be6c0134684a4ac8872a069348786a26e47efaf8d41a0886a771d4e7af e15ef7df-fe5a-11ef-b15e-00155d000105 https://dk.um.si/Dokument.php?lang=slv&id=189158 https://doi.org/10.7151/dmgt.2320 0 a5140bec-fe57-11ef-b15e-00155d000105 https://dk.um.si/Dokument.php?lang=slv&id=189157 Fakulteta za naravoslovje in matematiko Pedagoška fakulteta 0 0 0