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