{"id":"arxiv/2609.24097","url":"https://arxiv.org/abs/2609.24097","tags":["math.CO"],"score":0,"title":"Bounded chromatic number of graphs with small clique number and large minimum degree","domain":"math.CO","source":"arxiv","authors":["Jiaao Li","Xinyuan Li"],"reviews":0,"subject":"math.CO","summary":"We prove that every triangle-free graph with minimum degree at least $\\frac{n}{3}$ is $4$-colorable and thereby settle a problem of Brandt and Thomassé (2005) at the threshold $\\frac{n}{3}$. The number four is best possible. For a positive integer-valued function $f(n)=o(n)$, we relate the chromatic number of $f(n)$-vertex subgraphs of the Kneser graph $KG(n,f(n))$ to that of triangle-free graphs with minimum degree at least $\\frac{n}{3}-f(n)$. Consequently, for every $0 0$, and for all sufficiently large $n$, every $n$-vertex triangle-free graph with minimum degree at least…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-21","reactions":{}}