χ_f to Hall ratio gap growth rate

Status partial high confidence

Problem 4 asks for the exact growth rate of the smallest function $g$ such that $\chi_f(G) \leq \rho(G)\,g(|V(G)|)$ for all graphs $G$; at the time of posting the bounds were $\Omega(\log\log n) \leq g(n) \leq O(\log n)$. Steiner (2024, arXiv:2411.16465, published in Combinatorica) substantially narrows this gap by proving a lower bound of $\Omega(\log n/(\log\log n)^3)$, establishing $g(n) = (\log n)^{1-o(1)}$ and showing the growth rate is essentially logarithmic. The exact smallest $g$ (precise constant factors) remains undetermined, so the problem is partially resolved.

Cited literature (1)

• partial Fractional chromatic number vs. Hall ratio (2024)
  Raphael Steiner · Combinatorica · arXiv:2411.16465 · doi:10.1007/s00493-025-00164-0

  Proves $g(n) = (\log n)^{1-o(1)}$ by establishing a lower bound of $\Omega(\log n/(\log\log n)^3)$, reducing the gap from $[\Omega(\log\log n),\, O(\log n)]$ to essentially $\Theta(\log n)$ up to lower-order factors, and additionally constructs graphs with bounded Hall ratio, arbitrarily large fractional chromatic number, and good degree-weighted independence number in every subgraph (Theorem 1.5).

Reviewer notes. Steiner's paper (arXiv:2411.16465) is the primary follow-up; it nearly resolves Problem 4 by showing g(n)=(log n)^{1-o(1)}, collapsing an exponential gap to a polylogarithmic one. The exact smallest g (constant factors) is still open. The Dvořák 2007.11853 internal-ref entries appear to be false positives unrelated to Problem 4.

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