Tight bound on odd-wheel-free k-colorability

Conjecture on sharpness of Theorem 1.5 · arXiv:2102.10220

arXiv Conjecture high confidence— first stated 2021-03-19

Authors: Jacob Fox, Zoe Himwich, Nitya Mani

Status open high confidence

The conjecture that the bound $h(n, k, W_{2r+1}) \leq c_r n^2/k^{2-1/(r+1)}$ is tight up to a constant factor appears to remain open as of May 2026. A survey of all 7 papers citing arXiv:2102.10220 via the Semantic Scholar API reveals no follow-up that establishes a matching lower bound for odd wheels; the citing literature focuses instead on MaxCut and odd-cycle-free graph structure. The sole internal reference (arXiv:2105.03956, Scott–Seymour–Spirkl 2022) is a clear mismatch: that paper proves a Fox conjecture about pure pairs in perfect graphs, which is unrelated to $h(n,k,W_{2r+1})$.

Reviewer notes. No follow-up proving or disproving the odd-wheel tightness conjecture was found among the 7 known citing papers (retrieved via Semantic Scholar API). The conjecture is open with high confidence: the paper is ~5 years old, has a modest citation count, and the closest citing work addresses MaxCut rather than the $h(n,k,H)$ function for wheels.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Conjecture. For each positive integer $r$, the bound $$h(n, k, W_{2r+1}) \leq c_r \frac{n^2}{k^{2 - 1/(r+1)}}$$ is tight up to the constant factor $c_r$ depending on $r$.

Context

Theorem 1.5 gives the upper bound $h(n,k,W_{2r+1}) \leq c_r n^2/k^{2-1/(r+1)}$ for odd wheels when $n \geq k \geq 2$. The authors conjecture this is tight, by analogy with their matching lower bounds in the odd-cycle case.

Source paper

Making an $H$-Free Graph $k$-Colorable
Jacob Fox, Zoe Himwich, Nitya Mani · 2021-03-19
https://arxiv.org/abs/2102.10220 PDF source