On two conjectures of Hoàng
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866913107793674240 |
|---|---|
| author | Chen, Hongzhang Lan, Kaiyang Zhong, Wenlong |
| author_facet | Chen, Hongzhang Lan, Kaiyang Zhong, Wenlong |
| contents | 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 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^{ω-1}$. Hoàng conjectured that every even-hole-free graph is 3-divisible. We confirm this conjecture. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_09293 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | On two conjectures of Hoàng Chen, Hongzhang Lan, Kaiyang Zhong, Wenlong Combinatorics 05C15, 05C38, 05C69 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 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^{ω-1}$. Hoàng conjectured that every even-hole-free graph is 3-divisible. We confirm this conjecture. |
| title | On two conjectures of Hoàng |
| topic | Combinatorics 05C15, 05C38, 05C69 |
| url | https://arxiv.org/abs/2605.09293 |