Notes on complexity of packing coloring

Date
2018-09-01
Authors
Kim, Minki
Lidicky, Bernard
Lidicky, Bernard
Masarik, Tomas
Pfender, Florian
Major Professor
Advisor
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Altmetrics
Authors
Research Projects
Organizational Units
Mathematics
Organizational Unit
Journal Issue
Series
Department
Mathematics
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.

Comments

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.

Description
Keywords
Citation
DOI
Collections