Abstract
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.