Exponential order of K_r-free degenerate χ=d+1 graphs
Problem 6.3 · arXiv:2601.15245
Status open high confidence
Problem 6.3 asks whether every $K_r$-free $d$-degenerate graph with chromatic number $d+1$ must have $e^{\Omega_r(d)}$ vertices, extending the paper's main result from the triangle-free case ($r=3$) to all $r$. The source paper establishes the $r=3$ case, proving $e^{\Omega(d)} \le f(d) \le e^{O(d^2 \log d)}$ for triangle-free $d$-degenerate graphs, but leaves the general $r$ case open. No follow-up resolving this problem was found in a wide literature search conducted in May 2026.
Reviewer notes. The paper is very recent (January 2026). The triangle-free case ($r=3$) is settled by the main results of arXiv:2601.15245 itself. For general $r \ge 4$, the paper shows that $K_r$-free $d$-degenerate graphs can have fractional chromatic number $\Omega_r(d/\log^{r-2} d)$, but whether the minimum order of a $(d+1)$-chromatic example must be exponential in $d$ (Problem 6.3) remains unresolved. No citing or follow-up paper addressing this problem was identified.
Context
The main results of the paper establish that triangle-free $d$-degenerate graphs with at most $2^{cd}$ vertices have chromatic number strictly less than $d+1$; this problem asks whether the exponential lower bound on the order of extremal examples extends from the triangle-free case ($r=3$) to all $r$.
Source paper
Coloring small locally sparse degenerate graphs and related problems
Domagoj Bradač, Jacob Fox, Raphael Steiner, Benny Sudakov, Shengtong Zhang · 2026-01-21
https://arxiv.org/abs/2601.15245