Huang–Zhou–Chang's 5/4 coloring conjecture for even-hole-free graphs

A hole is an induced cycle of length at least four, and a graph is even-hole-free if it has no hole of even length. For a graph GG, let χ(G)\chi(G) denote its chromatic number and ω(G)\omega(G) its clique number. Huang–Zhou–Chang's conjecture. Every even-hole-free graph GG satisfies

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

Every even-hole-free graph is known to satisfy χ(G)2ω(G)1\chi(G)\leq 2\omega(G)-1, but whether that bound is best possible remains open. The conjecture proposes the sharper linear coloring bound above.

Sources & referencesView supporting material

Primary source

Feng Liu, Shuang Sun and Yan Wang, “Optimal coloring of \cap,even\ hole\-free graphs with no short odd holes”, arXiv:2607.25396 (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.