Yidong Zhou

collaborators

4 papers

math.CO2026

ErdÅs-Hajnal beyond the five-vertex path

Shenwei Huang, Yiao Ju, Yidong Zhou

The well-known ErdÅ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…

math.CO2026

The optimal chromatic bound for even-hole-free graphs without induced seven-vertex paths

Shenwei Huang, Yidong Zhou, Yeonsu Chang

The class of even-hole-free graphs has been extensively studied on its own and on its relation to perfect graphs. In this paper, we study the $I ¨ $ -boundedness of even-hole-free gra…

math.CO2025

Three-coloring triangle-free graphs without long forbidden paths

Yidong Zhou, Jorik Jooken, Baoyuan Shan +2

A graph $G$ is $k$ -vertex-critical if $I ¨ (G) = k$ , but $I ¨ (G^{'}) < k$ for every proper induced subgraph $G^{'}$ of $G$ . For a family of graphs $F$ , $G$ is $F$ -free if no…

math.CO2025

3-Coloring $P_{t}$ -Free Graphs With Only One Prescribed Induced Odd Cycle Length

Yidong Zhou, Mingxian Zhong, Shenwei Huang

A graph is $P_{t}$ -free if it contains no induced subgraph isomorphic to a $t$ -vertex path. A graph is not bipartite if and only if it contains an induced subgraph isomorphic to a $k…

ErdÅs-Hajnal beyond the five-vertex path

The optimal chromatic bound for even-hole-free graphs without induced seven-vertex paths

Three-coloring triangle-free graphs without long forbidden paths

3-Coloring Pt​-Free Graphs With Only One Prescribed Induced Odd Cycle Length

ErdÅs-Hajnal beyond the five-vertex path

3-Coloring $P_{t}$ -Free Graphs With Only One Prescribed Induced Odd Cycle Length