Author

Yi-Dong Zhou

2 papers indexed here

We haven’t gathered this author’s papers yet. Follow them and we’ll fetch their work.

Not the right person? Other researchers publish under this name.

Preprint Nov 2026

The Erd\H{o}s--Hajnal property for paths

The well-known Erd\H{o}s-Hajnal conjecture states that for any graph $H$, there is a constant $c=c(H)>0$ such that every $n$-vertex graph $G$ with no induced copies of $H$ contains a clique or an independent set of size at least $n^{c}$. In this paper, we prove that the Erd\H{o}s-Hajnal conjecture holds for every path.

Shen-Wei Huang, Yi-Dong Zhou, Yuwen Zhou · 0 citations

Preprint Oct 2026

A quasi-polynomial $\chi$-bound for $P_6$-free graphs

In this paper we prove that every graph $G$ with no induced six-vertex path satisfies $\chi(G)\le \omega(G)^{c\log_2\omega(G)}$ for $c=45/\log_2(4/3)<109$. The best previous bound was exponential in $\omega(G)$. Our result is the first quasi-polynomial bound for $P_6$-free graphs and generalizes the bound for $P_5$-fre...

Shen-Wei Huang, Yi-Dong Zhou, Yuwen Zhou · 0 citations