| Title: | A survey on packing colorings |
|---|
| Authors: | ID Brešar, Boštjan (Author)
ID Ferme, Jasmina (Author)
ID Klavžar, Sandi (Author)
ID Rall, Douglas F. (Author) |
|---|
| Files: |  Bresar-2020-A_SURVEY_ON_PACKING_COLORINGS.pdf (98,49 KB)
MD5: 472514A70A4C09C93A3C6E62D459DF5B
 https://doi.org/10.7151/dmgt.2320
|
|---|
| Language: | English |
|---|
| Work type: | Scientific work |
|---|
| Typology: | 1.02 - Review Article |
|---|
| Organization: | FNM - Faculty of Natural Sciences and Mathematics
PEF - Faculty of Education
|
|---|
| Abstract: | 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. |
|---|
| Keywords: | packing coloring, packing chromatic number, subcubic graph, S-packing chromatic number, computational complexity |
|---|
| Publication status: | Published |
|---|
| Publication version: | Version of Record |
|---|
| Submitted for review: | 31.01.2020 |
|---|
| Article acceptance date: | 08.04.2020 |
|---|
| Publisher: | Technical University Press |
|---|
| Year of publishing: | 2020 |
|---|
| Number of pages: | Str. 923-970 |
|---|
| Numbering: | Letn. 40, št. 4 |
|---|
| PID: | 20.500.12556/DKUM-92011  |
|---|
| UDC: | 519.17 |
|---|
| ISSN on article: | 1234-3099 |
|---|
| COBISS.SI-ID: | 23220483 |
|---|
| DOI: | 10.7151/dmgt.2320 |
|---|
| Publication date in DKUM: | 11.03.2025 |
|---|
| Views: | 279 |
|---|
| Downloads: | 21 |
|---|
| Metadata: |    |
|---|
| Categories: | Misc.
|
|---|
|
:
|
Copy citation |
|---|
| | | | Average score: | (0 votes) |
|---|
| Your score: | Voting is allowed only for logged in users. |
|---|
| Share: |  |
|---|
Hover the mouse pointer over a document title to show the abstract or click
on the title to get all document metadata. |
