Complexity of the packing coloring problem for trees (Q972338)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Complexity of the packing coloring problem for trees
scientific article

    Statements

    Complexity of the packing coloring problem for trees (English)
    0 references
    0 references
    0 references
    25 May 2010
    0 references
    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)\).
    0 references
    packing coloring
    0 references
    computational complexity
    0 references
    graph algorithm
    0 references
    tree
    0 references
    chordal graph
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references