Polynomial instances of the Packing Coloring Problem

A packing k-coloring of a graph G is a k-coloring such that the distance between two vertices having color i is at least i + 1 . The packing chromatic number of G, χ ρ ( G ) , is the minimum k such that G has a packing k-coloring. To compute the packing chromatic number is NP-hard, even restricted to trees. s work, we prove that χ ρ ( G ) can be computed in polynomial time for the class of partner limited graphs and for an infinite subclass of lobster graphs, including caterpillars.