The five-holed graph chromatic bound conjecture

A graph GG is 55-holed if every induced cycle of GG of length at least four has length exactly five. Let χ(G)\chi(G) and ω(G)\omega(G) denote the chromatic and clique numbers of GG.

Five-holed graph chromatic bound conjecture. If GG is 55-holed, then

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

The paper proves the analogous bound for odd 7\ell\geq 7 and proposes this as the remaining five-holed case; the source gives no resolution of the conjecture.

Sources & referencesView supporting material

Primary source

Yan Wang and Rong Wu, “Optimal χ-boundness of -holed graphs”, arXiv:2508.07034 (2025).

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.