On minimal nonperfectly divisible fork-free graphs

Abstract

A fork is a graph obtained from $K_{1,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 $\ddot{I}‰(H[B])<\ddot{I}‰(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\in \{P_7,P_6\cup K_1\}$, each (fork, $F$)-free graph $G$ is perfectly divisible and hence $\ddot{I}‡(G)\le \left(\genfrac{}{}{0ex}{}{\ddot{I}‰(G)+1}{2}\right)$.