Perfect divisibility and 2-divisibility

Abstract

A graph $G$ is said to be $2$-divisible if for all (nonempty) induced subgraphs $H$ of $G$, $V(H)$ can be partitioned into two sets $A,B$ such that $\ddot{I}‰(A)<\ddot{I}‰(H)$ and $\ddot{I}‰(B)<\ddot{I}‰(H)$. A graph $G$ is said to be perfectly divisible if for all induced subgraphs $H$ of $G$, $V(H)$ can be partitioned into two sets $A,B$ such that $H[A]$ is perfect and $\ddot{I}‰(B)<\ddot{I}‰(H)$. We prove that if a graph is $(P_5,C_5)$-free, then it is $2$-divisible. We also prove that if a graph is bull-free and either odd-hole-free or $P_5$-free, then it is perfectly divisible.