{"id":"arxiv/2605.09293","url":"https://arxiv.org/abs/2605.09293","tags":["math.CO"],"score":0,"title":"On two conjectures of Hoàng","domain":"math.CO","source":"arxiv","authors":["Hongzhang Chen","Kaiyang Lan","Wenlong Zhong"],"reviews":0,"subject":"math.CO","summary":"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 $ω(B) < ω(H)$. It is easy to see that the chromatic number of a perfectly divisible graph is at most $\\binom{ω(G)+1}{2}$. Hoàng conjectured that every graph $G$ with $α(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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-05-10","reactions":{}}