Coloring triangle-free degenerate graphs via LLL

Problem 6.2 · arXiv:2601.15245

arXiv Problem high confidence— first stated 2026-01-21

Authors: Domagoj Bradač, Jacob Fox, Raphael Steiner, Benny Sudakov, Shengtong Zhang

Status open high confidence

Problem 6.2 asks whether, for every $\varepsilon>0$, each $d$-degenerate triangle-free graph with $\Delta(G)\leq e^{d^{1-\varepsilon}}$ satisfies $\chi(G)=O(d/\log d)$. An affirmative answer would have consequences for immersion analogues of Hadwiger's conjecture. No follow-up resolving this January 2026 problem was found in the May 2026 review.

Reviewer notes. The exact conclusion was restored from the cached arXiv HTML theorem environment.

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

Problem. Is the following statement true for all $\varepsilon>0$? If $G$ is a $d$-degenerate triangle-free graph with maximum degree $\Delta(G)\leq e^{d^{1-\varepsilon}}$, then we have $\chi(G)=O\left(\frac{d}{\log d}\right)$.

Context

Resolving this problem would likely require localizing the random coloring process used in the paper so that the union bound can be replaced by an application of the Lovász Local Lemma. An affirmative answer would imply results on immersion analogues of Hadwiger's conjecture, as conjectured by Lescure and Meyniel in 1988.

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