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

Less than 1 year old · traced to

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.

References

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.