On two conjectures of Hoà ng

Abstract

A graph $G$ is said to be perfectly divisible if for every induced subgraph $H$ of $G$ with at least one edge, the vertex set $V(H)$ can be partitioned into two sets $A,B$ such that $H[A]$ is perfect and $\ddot{I}‰(B)<\ddot{I}‰(H)$. It is easy to see that the chromatic number of a perfectly divisible graph is at most $\left(\genfrac{}{}{0ex}{}{\ddot{I}‰(G)+1}{2}\right)$. Hoà ng conjectured that every graph $G$ with $\hat{I}\pm (G)\le 3$ is perfectly divisible. We disprove this conjecture. In the same vein, a graph $G$ with at least one edge is $k$-divisible if for every induced subgraph $H$ of $G$ with at least one edge, the vertex set $V(H)$ can be partitioned into $k$ sets, none of which contains a largest clique of $H$. It is easy to see that the chromatic number of a $k$-divisible graph is at most $k^{\ddot{I}‰-1}$. Hoà ng conjectured that every even-hole-free graph is 3-divisible. We confirm this conjecture.

5 pages, any comments and suggestions are welcome