The Bounded-VC chromatic thresholds of graphs
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$.…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2608.27068
curl -X POST /api/v1/records/arxiv/2608.27068/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.27068/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'