Complexity of the packing coloring problem for trees (Q972338): Difference between revisions

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)\).