The Packing Coloring Problem on P4-tidy Graphs

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

Congreso; ALIO-INFORMS Joint International Meeting; 2010

A \emph{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 \emph{packing chromatic number} of $G$, $\chi_{p}(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 the class of perfect graphs.. In this work, we prove that $\chi_{p}(G)$ can be computed in polynomial time if $G$ belongs to the class of $P_4$-tidy graphs, that includes the perfect classes of $P_4$-sparse graphs and cographs .\end{abstract}