Skip to main content
Notes on complexity of packing coloring
Information Processing Letters
  • Minki Kim, KAIST
  • Bernard Lidicky, Iowa State University
  • Tomas Masarik, Charles University, Prague
  • Florian Pfender, University of Colorado, Denver
Document Type
Publication Version
Submitted Manuscript
Publication Date

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.


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.

Copyright Owner
Elsevier B.V.
File Format
Citation Information
Minki Kim, Bernard Lidicky, Tomas Masarik and Florian Pfender. "Notes on complexity of packing coloring" Information Processing Letters Vol. 137 (2018) p. 6 - 10
Available at: