On minimal nonperfectly divisible fork-free graphs

A fork is a graph obtained from K1,3 (usually called claw) by subdividing an edge once. A graph is perfectly divisible if for each of its induced subgraph H, $V(H)$ can be partitioned into A and B such that $H[A]$ is perfect and ω(H[B]) < ω(H). In this paper, we prove that the perfect divisibility of fork-free graphs is equivalent to that of claw-free graphs. We also prove that, for F∈ ₇, P₆∪ K₁\, each (fork, F)-free graph G is perfectly divisible and hence χ(G)≤ ω(G)+12.