Polynomial instances of the Packing Coloring Problem

G. R. ARGIROFFO; G. NASINI; P. D. TORRES

Electronic Notes in Discrete Mathematics

Elsevier

Año: 2011 vol. 37 p. 363 - 368

1571-0653

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, $chi_{rho}(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 $chi_{rho}(G)$ can be computed in polynomial time for the class of partner limited graphs and for an infinite subclass of lobster graphs, including caterpillars.