On two conjectures of Hoàng

A graph 𝐺 is said to be perfectly divisible if for every induced subgraph 𝐻 of 𝐺 with at least one edge, the vertex set 𝑉 ⁡ ( 𝐻 ) can be partitioned into two sets 𝐴 , 𝐵 such that 𝐻 ⁡ [ 𝐴 ] is perfect and 𝜔 ⁡ ( 𝐵 ) < 𝜔 ⁡ ( 𝐻 ) . It is easy to see that the chromatic number of a perfectly divisible graph 𝐺 is at most ( 𝜔 ⁡ ( 𝐺 ) + 1 2 ) . Hoàng conjectured that every graph 𝐺 with 𝛼 ⁡ ( 𝐺 ) ≤ 3 is perfectly divisible. We disprove this conjecture. In the same vein, a graph 𝐺 with at least one edge is 𝑘 -divisible if for every induced subgraph 𝐻 of 𝐺 with at least one edge, the vertex set 𝑉 ⁡ ( 𝐻 ) can be partitioned into 𝑘 sets, none of which contains a maximum clique of 𝐻 . Analogously, it is easy to see that the chromatic number of a 𝑘 -divisible graph 𝐺 is at most 𝑘 𝜔 ⁡ ( 𝐺 ) − 1 . Hoàng conjectured that every even-hole-free graph is 3-divisible. We confirm this conjecture.