Sub-exponential vertex threshold for degenerate coloring
Problem 6.1 · arXiv:2601.15245
Status open high confidence
Problem 6.1 of arXiv:2601.15245 asks whether the upper bound $2^{cd}$ on the number of vertices in Theorems 1.1 and 1.2 can be weakened to $e^{\omega(d)}$, with a corresponding improvement of the chromatic number bound, and whether large constant girth additionally helps. The paper itself establishes $e^{\Omega(d)} \leq f(d) \leq e^{O(d^2 \log d)}$ for the minimum order of a $d$-degenerate triangle-free $(d+1)$-chromatic graph, showing an exponential gap between the lower bound on $f(d)$ and the vertex regime covered by the main theorems. No follow-up resolving or making partial progress on Problem 6.1 has been found in the literature as of May 2026, which is expected given the paper's January 2026 submission date.
Reviewer notes. No follow-up found. The conjecture is very recent (January 2026). The key open gap is between the vertex regime $n \leq 2^{cd}$ covered by the main theorems and the sub-exponential regime $n = e^{\omega(d)}$; resolving it is noted by the authors as the most important open problem from their paper and would have implications for Erd\H{o}s's problem on graph Ramsey numbers for triangle-free graphs.
Context
The perhaps most important open problem left by the paper is whether the exponential requirement on the number of vertices in Theorems 1.1 and 1.2 can be further relaxed. Even improving the constant $c$ in Theorem 1.1 could resolve Erdős's problem on graph Ramsey numbers for all triangle-free graphs by combining with the trivial lower bound $r(G)\geq|V(G)|$.
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