The optimal chromatic bound for even-hole-free graphs without induced seven-vertex paths
Shenwei Huang, Yidong Zhou, Yeonsu Chang · 2026
Read The optimal chromatic bound for even-hole-free graphs without induced seven-vertex paths by Shenwei Huang, Yidong Zhou, Yeonsu Chang (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-04403.txt.
Description
Shenwei Huang and 2 co-authors prove an optimal coloring bound for a restricted graph class in a 2026 paper. Even-hole-free graphs, those with no even cycle as an induced pattern, resist the usual coloring guarantees. The authors additionally forbid induced seven-vertex paths.
Every such graph's chromatic number is at most five quarters of its clique number, rounded up, and the bound cannot be improved. The result extends an earlier theorem for six-vertex paths and confirms Reed's conjecture for this class. The proof leans on structural analysis of a maximal configuration built from a five-cycle. Chi-boundedness results like this map where coloring stays close to clique size.
Catalog record
| CREATOR | Shenwei Huang, Yidong Zhou, Yeonsu Chang |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 334 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2602-04403