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 ω² 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₅-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₅-free graphs. We will show that recognizing perfectly divisible graphs is NP-hard.