Notes on complexity of packing coloring

DOI10.1016/j.ipl.2018.04.012zbMath1478.68247arXiv1712.08373OpenAlexW2776807883MaRDI QIDQ1641149

Florian Pfender, Bernard Lidický, Tomáš Masařík, 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 algorithmschordal graphsinterval graphsparameterized complexitypacking coloring

Mathematics Subject Classification ID

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

Related Items

Parameterized Complexity of Geodetic Set ⋮ Packing chromatic numbers of finite super subdivisions of graphs ⋮ Grundy Distinguishes Treewidth from Pathwidth ⋮ A survey on packing colorings ⋮ On the packing chromatic number of Moore graphs ⋮ Unnamed Item ⋮ \(\mathcal{U}\)-bubble model for mixed unit interval graphs and its applications: the MaxCut problem revisited ⋮ Parameterized Complexity of Geodetic Set ⋮ Graphs that are critical for the packing chromatic number

Cites Work

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