The packing coloring problem for lobsters and partner limited graphs

A packing  kk-coloring   of a graph GG is a kk-coloring such that the distance between two vertices having color ii is at least i+1i+1.To compute the packing chromatic number is NP-hard, even restricted to trees, and it is known to be polynomial time solvable only for a few graph classes, including cographs and split graphs.In this work, we provide upper bounds for the packing chromatic number of lobsters and we prove that it can be computed in polynomial time for an infinite subclass of them, including caterpillars.In addition, we provide superclasses of split graphs where the packing chromatic number can be computed in polynomial time. Moreover, we prove that the packing chromatic number can be computed in polynomial time for the class of partner limited graphs, a superclass of cographs, including also P4P4-sparse and P4P4-tidy graphs.