Complexity of the packing coloring problem for trees Original Research Article

Packing coloring is a partitioning of the vertex set of a graph with the property that vertices in the image-th class have pairwise distance greater than image. The main result of this paper is a solution of an open problem of Goddard et al. showing that the decision whether a tree allows a packing coloring with at most image classes is NP-complete.