The 5/4 chromatic bound conjecture for even-hole-free graphs

Let GG be an even-hole-free graph, meaning that GG has no induced cycle of even length at least four. Write χ(G)\chi(G) for its chromatic number and ω(G)\omega(G) for its clique number. The 5/4 bound conjecture. For every even-hole-free graph GG,

χ(G)54ω(G).\chi(G)\leq \left\lceil \frac{5}{4}\omega(G) \right\rceil.

The paper proves the same bound for the subclass of (P7,(P_7, even-hole))-free graphs and notes that equal-size blowups of C5C_5 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

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.