Campus Units

Mathematics

Document Type

Article

Publication Version

Submitted Manuscript

Publication Date

9-2018

Journal or Book Title

Information Processing Letters

Volume

137

First Page

6

Last Page

10

DOI

10.1016/j.ipl.2018.04.012

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.

Copyright Owner

Elsevier B.V.

Language

en

File Format

application/pdf

Published Version

Included in

Mathematics Commons

Share

COinS