{"id":"arxiv/2601.15245","url":"https://arxiv.org/abs/2601.15245","tags":["math.CO"],"score":0,"title":"Coloring small locally sparse degenerate graphs and related problems","domain":"math.CO","source":"arxiv","authors":["Domagoj Bradač","Jacob Fox","Raphael Steiner","Benny Sudakov","Shengtong Zhang"],"reviews":0,"subject":"math.CO","summary":"The classic upper bound on the chromatic number of $d$-degenerate graphs is $d+1$, shown to be tight by complete graphs. A natural question is whether this bound remains tight if one forbids large cliques. Classic constructions of Tutte and Zykov from the early 50s show that there exist $d$-degenerate $(d+1)$-chromatic graphs that are triangle-free, however these constructions grow rapidly with $d$. Motivated by this and addressing a problem posed by the second author at the Oberwolfach Graph Theory workshop, we prove that the minimum order $f(d)$ of a $d$-degenerate triangle-free graph of…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-01-21","reactions":{}}