Notes on complexity of packing coloring

Abstract

A packing $k$-coloring for some integer $k$ of a graph $G=(V,E)$ is a mapping $\phi :V\to \{1,\dots ,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 \emph{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.

9 pages, 2 figures

References in corpus (2)

• Shrub-depth: Capturing Height of Dense Graphs
• Packing chromatic number of subcubic graphs

Cited by in corpus (1)

• U-Bubble Model for Mixed Unit Interval Graphs and its Applications: The MaxCut Problem Revisited