Notes on complexity of packing coloring

Date
2018-09-01
Authors
Kim, Minki
Lidicky, Bernard
Masarik, Tomas
Pfender, Florian
Journal Title
Journal ISSN
Volume Title
Publisher
Altmetrics
Authors
Research Projects
Organizational Units
Mathematics
Organizational Unit
Journal Issue
Series
Abstract

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.

Description

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.

Keywords
Citation
DOI
Collections