The 5/4 chromatic bound conjecture for even-hole-free graphs
The 5/4 chromatic bound conjecture for even-hole-free graphs
Let be an even-hole-free graph, meaning that has no induced cycle of even length at least four. Write for its chromatic number and for its clique number. The 5/4 bound conjecture. For every even-hole-free graph ,
The paper proves the same bound for the subclass of even-hole-free graphs and notes that equal-size blowups of suggest optimality, but the full even-hole-free case remains open.
Sources & referencesView supporting material
Primary source
Shenwei Huang, Yidong Zhou and Yeonsu Chang, “The optimal chromatic bound for even-hole-free graphs without induced seven-vertex paths”, arXiv:2602.04403 (2026).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.