Notes on complexity of packing coloring
share
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 -complete for diameter exactly 5. While the problem is easy to solve for diameter 2, we show -completeness for any diameter at least 3. Our reduction also shows that the packing chromatic number is hard to approximate within n^1/2-ε for any ε > 0. In addition, we design an 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.
READ FULL TEXT