On the structure of perfectly divisible graphs

A graph G is perfectly divisible if every induced subgraph H of G contains a set X of vertices such that X meets all largest cliques of H , and X induces a perfect graph. The chromatic number of a perfectly divisible graph G is bounded by ω 2 where ω denotes the number of vertices in a largest clique of G . A graph G is minimally non-perfectly divisible if G is not perfectly divisible but each of its proper induced subgraph is. A set C of vertices of G is a clique cutset if C induces a clique in G , and G − C is disconnected. We prove that a P 5 -free minimally non-perfectly divisible graph cannot contain a clique cutset. This result allows us to re-establish several theorems on the perfect divisibility of some classes of P 5 -free graphs. We will show that recognizing perfectly divisible graphs is NP-hard.