Notes on complexity of packing coloring
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F18%3A10385822" target="_blank" >RIV/00216208:11320/18:10385822 - isvavai.cz</a>
Result on the web
<a href="https://doi.org/10.1016/j.ipl.2018.04.012" target="_blank" >https://doi.org/10.1016/j.ipl.2018.04.012</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1016/j.ipl.2018.04.012" target="_blank" >10.1016/j.ipl.2018.04.012</a>
Alternative languages
Result language
angličtina
Original language name
Notes on complexity of packing coloring
Original language description
A packing k-coloring for some integer k of a graph G = (V, E) is a mapping phi : V -> {1, . . . , k} such that any two vertices u, v of color phi(u) = phi(v) are in distance at least phi(u) + 1. This concept is motivated by frequency assignment problems. The packing chromatic number of G is the smallest k such that there exists a packing k-coloring of G. Fiala and Golovach showed that determining the packing chromatic number for chordal graphs is NP-complete for diameter exactly 5. While the problem is easy to solve for diameter 2, we show NP-completeness for any diameter at least 3. Our reduction also shows that the packing chromatic number is hard to approximate within n(1/)(2-epsilon) for any epsilon > 0. In addition, we design an FPT algorithm for interval graphs of bounded diameter. This leads us to exploring the problem of finding a partial coloring that maximizes the number of colored vertices.
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
<a href="/en/project/GA17-09142S" target="_blank" >GA17-09142S: Modern algorithms: New challenges of complex data sets</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2018
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Information Processing Letters
ISSN
0020-0190
e-ISSN
—
Volume of the periodical
137
Issue of the periodical within the volume
9
Country of publishing house
NL - THE KINGDOM OF THE NETHERLANDS
Number of pages
5
Pages from-to
6-10
UT code for WoS article
000438480600002
EID of the result in the Scopus database
2-s2.0-85046782814