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

CREATORShenwei Huang, Yidong Zhou, Yeonsu Chang
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE334 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2602-04403

Browse the full library · About the Tower of Babel