Coloring triangle-free degenerate graphs via LLL
Problem 6.2 · arXiv:2601.15245
Status open high confidence
Problem 6.2 from arXiv:2601.15245 asks whether every $d$-degenerate triangle-free graph with maximum degree at most $e^{d^{1-\varepsilon}}$ satisfies some chromatic upper bound (full statement truncated in source); an affirmative answer would imply immersion analogues of Hadwiger's conjecture as conjectured by Lescure and Meyniel (1988). The paper was posted in January 2026 and no subsequent preprint or journal article resolving or making partial progress on this specific problem was found in web searches conducted in May 2026. The closely related paper arXiv:2501.18238 (Martinsson, January 2025) proves triangle-free $d$-degenerate graphs have fractional chromatic number at most $(4+o(1))d/\ln d$, but predates the source paper and does not reference Problem 6.2.
Reviewer notes. No follow-up found. The conjecture is very recent (January 2026). The key challenge noted in the paper is localizing the random coloring process to allow use of the Lovász Local Lemma in place of a union bound. A related preprint arXiv:2501.18238 (Martinsson 2025) on fractional chromatic number of triangle-free d-degenerate graphs predates the source paper and is not a follow-up to Problem 6.2.
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.
Notes. The conclusion of the problem statement is truncated in the provided source; only the hypothesis is visible.
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