Perfectly colorable graphs
We define a perfect coloring of a graph G as a proper coloring of G such that every connected induced subgraph H of G uses exactly omega(H) many colors where omega(H) is the clique number of H. A graph is perfectly colorable if it admits a perfect coloring. We show that the class of perfectly colorable graphs is exactly the class of perfect paw-free graphs. It follows that perfectly colorable graphs can be recognized and colored in linear time. (C) 2011 Elsevier B.V. All rights reserved.
perfectly colorable graphs perfect coloring perfect paw-free graphs combinatorial problems perfect graphs