{"id":"arxiv/2608.27068","url":"https://arxiv.org/abs/2608.27068","tags":["math.CO"],"score":0,"title":"The Bounded-VC chromatic thresholds of graphs","domain":"math.CO","source":"arxiv","authors":["Jinze Hu","Qinghai Liu","Liping Zhang","Yanmei Hong"],"reviews":0,"subject":"math.CO","summary":"For a graph $H$, the chromatic threshold $δ_χ(H)$ is the infimum of $c>0$ such that the chromatic number of every $n$-vertex $H$-free graph with minimum degree at least $cn$ is bounded by a constant depending only on $H$ and $c$. Allen, Böttcher, Griffiths, Kohayakawa, and Morris proved that if $χ(H)=r\\geq 3$, then $δ_χ(H)\\in\\{\\frac{r-3}{r-2}, \\frac{2r-5}{2r-3}, \\frac{r-2}{r-1}\\}$. Liu, Shangguan, Skokan, and Xu introduced the bounded-VC chromatic threshold $\\text{VC}(H)$ by restricting the host graphs to have bounded VC-dimension. We determine this parameter for graph $H$ with $χ(H)\\ge 3$.…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-08-27","reactions":{}}