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.In this 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.