Notes on complexity of packing coloring

DOI10.1016/J.IPL.2018.04.012MaRDI QIDQ1641149zbMATH OpenOpenAlexFDO

Authors Bernard Lidický, Tomáš Masařík, Florian Pfender, Min-Ki Kim

Publication date 15 June 2018

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1712.08373

zbMATH Keywords

graph algorithmsinterval graphschordal graphsparameterized complexitypacking coloring

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Coloring of graphs and hypergraphs (05C15) Graph representations (geometric and intersection representations, etc.) (05C62) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Parameterized complexity, tractability and kernelization (68Q27)

Abstract: A packing $k$-coloring for some integer $k$ of a graph $G=(V,E)$ is a mapping $varphi:Vo1,ldots,k$ such that any two vertices $u,v$ of color $varphi(u)=varphi(v)$ are in distance at least $varphi(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-varepsilon}$ for any $varepsilon>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.

Recommendations

• Complexity of the packing coloring problem for trees
• A note on packing chromatic number of the square lattice
• Complexity of the Packing Coloring Problem for Trees
• Polynomial instances of the packing coloring problem
• The packing coloring problem for \((q,q-4)\) graphs

Cites work

• scientific article; zbMATH DE number 7029306 (Why is no real title available?)
• scientific article; zbMATH DE number 2104737 (Why is no real title available?)
• A note on packing chromatic number of the square lattice
• Broadcast chromatic numbers of graphs
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Complexity of the packing coloring problem for trees
• Independent Sets in Asteroidal Triple-Free Graphs
• Linear time solvable optimization problems on graphs of bounded clique-width
• On the packing chromatic number of Cartesian products, hexagonal lattice, and trees
• Packing chromatic number of cubic graphs
• Parameterized Algorithms for Modular-Width
• Parameterized algorithms
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• The packing chromatic number of infinite product graphs
• The packing chromatic number of the infinite square lattice is between 13 and 15

Cited in

(16)

• Complexity of the Packing Coloring Problem for Trees
• Grundy Distinguishes Treewidth from Pathwidth
• Modeling the packing coloring problem of graphs
• On the packing chromatic number of Moore graphs
• Parameterized complexity of geodetic set
• The packing coloring problem for \((q,q-4)\) graphs
• The packing coloring problem for lobsters and partner limited graphs
• A survey on packing colorings
• Packing chromatic number of windmill related graphs and chain silicate networks
• Complexity of the packing coloring problem for trees
• Graphs that are critical for the packing chromatic number
• Polynomial instances of the packing coloring problem
• U-bubble model for mixed unit interval graphs and its applications: the MaxCut problem revisited
• \(\mathcal{U}\)-bubble model for mixed unit interval graphs and its applications: the MaxCut problem revisited
• Parameterized Complexity of Geodetic Set
• Packing chromatic numbers of finite super subdivisions of graphs

This page was built for publication: Notes on complexity of packing coloring

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1641149)