A packing k-coloring for some integer k of a graph G = (V, E) is a mapping ϕ : V → {1, . . . , k} such that any two vertices u, v of color ϕ(u) = ϕ(v) are in distance at least ϕ(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 n1/2−ε for any ε > 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.
Available at: http://works.bepress.com/bernard-lidicky/43/
This is a manuscript of an article published as Kim, Minki, Bernard Lidický, Tomáš Masařík, and Florian Pfender. "Notes on complexity of packing coloring." Information Processing Letters 137 (2018): 6-10. doi: 10.1016/j.ipl.2018.04.012. Posted wih permission.