Huang–Zhou–Chang's 5/4 coloring conjecture for even-hole-free graphs
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 , let denote its chromatic number and its clique number. Huang–Zhou–Chang's conjecture. Every even-hole-free graph satisfies
Every even-hole-free graph is known to satisfy , 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
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.