
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)\).
computational complexity, Applied Mathematics, Packing coloring, Graph algorithm, packing coloring, Trees, tree, Computational complexity, Chordal graph, chordal graph, Coloring of graphs and hypergraphs, Graph algorithms (graph-theoretic aspects), Graph theory (including graph drawing) in computer science, graph algorithm, Discrete Mathematics and Combinatorics
computational complexity, Applied Mathematics, Packing coloring, Graph algorithm, packing coloring, Trees, tree, Computational complexity, Chordal graph, chordal graph, Coloring of graphs and hypergraphs, Graph algorithms (graph-theoretic aspects), Graph theory (including graph drawing) in computer science, graph algorithm, Discrete Mathematics and Combinatorics
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 49 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 1% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
