Complexity of the packing coloring problem for trees
type: Item
instance of: scholarly article
title: Complexity of the packing coloring problem for trees
zbMATH Open document ID: 1219.05185
author: Jiří Fiala
author: Petr A. Golovach
published in: Discrete Applied Mathematics
publication date: 2010-05-25T00:00:00Z
review text: A packing \(k\)-colouring of a graph \(G=(V,E)\) is a list \((X_1, X_2, \dots, X_k)\) of sets with \(\bigcup_{i=1}^k X_i = V\), such that for every index \(i\) with \(1 \leq i \leq k\), every pair of different vertices \(u,v \in X_i\) has distance at least \(i\) in \(G\) [see \textit{B. Brešar}, \textit{S. Klavžar}, and \textit{D.F. Rall}, ``On the packing chromatic number of Cartesian products, hexagonal lattice, and trees,'' Discrete Appl.\ Math.\ 155, No.\,17, 2303--2311 (2007; Zbl 1126.05045)]. \textit{W. Goddard}, \textit{S.M. Hedetniemi}, \textit{S.T. Hedetniemi}, \textit{J.M. Harris}, and \textit{D.F. Rall} [``Broadcast chromatic numbers of graphs,'' Ars Comb. 86, 33--49 (2008; Zbl 1224.05172)] showed that it is NP-complete to decide whether a given graph has a packing \(4\)-colouring. The authors show that the packing colouring problem remains NP-complete when restricted to trees. For trees (and graphs of bounded treewidth) this problem becomes solvable in polynomial time if the diameter is bounded. When restricted to chordal graphs, the problem becomes fixed parameter tractable when parametrised by \(k\), and remains NP-complete when restricted to chordal graphs of diameter at most \(5\). The authors consider more general \(s\)-packing colourings too, where \(s\) is a nondecreasing function, and vertices in \(X_i\) are required to have pairwise distance at least \(s(i)\).
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 5711869
zbMATH Keywords: packing coloring
zbMATH Keywords: computational complexity
zbMATH Keywords: graph algorithm
zbMATH Keywords: tree
zbMATH Keywords: chordal graph
MaRDI profile type: Publication
full work available at URL: j.dam.2008.09.001
OpenAlex ID: W2151433687
cites work: Easy problems for tree-decomposable graphs
cites work: Q4288578
cites work: Q4699283
cites work: Generation of polynomial-time algorithms for some optimization problems on tree-decomposable graphs
cites work: On the packing chromatic number of Cartesian products, hexagonal lattice, and trees
cites work: The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
cites work: Linear time solvable optimization problems on graphs of bounded clique-width
cites work: Q4393480
cites work: Q4198056
cites work: Q3070232
cites work: Q4820787
DOI: 10.1016/J.DAM.2008.09.001
Recommended article: Complexity of the Packing Coloring Problem for Trees
Recommended article: Dichotomies properties on computational complexity of \(S\)-packing coloring problems
Recommended article: Packing problems in edge-colored graphs
Recommended article: Notes on complexity of packing coloring
Recommended article: The Packing Coloring Problem for (q,q-4) Graphs
Recommended article: Q3070232
Recommended article: Polynomial instances of the packing coloring problem
Recommended article: Graph packings
Recommended article: A survey on packing colorings
Recommended article: The packing coloring problem for lobsters and partner limited graphs
description: scientific article; zbMATH DE number 5711869