On chromatic number of countable graphs
This paper investigates when countable graphs have a finite or an infinite chromatic number through model theoretic methods. For Fraïssé limits, we show that instability forces the chromatic number to be infinite, yielding a complete classification of homogeneous graphs with a finite chromatic number. In contrast, Hrushovski construction always produces graphs of finite chromatic number, though the value can be made arbitrarily large. In tame settings -- such as stable graphs of $U$-rank one and graphs definable in o-minimal structures -- an infinite chromatic number necessarily yields…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2602.20667
curl -X POST /api/v1/records/arxiv/2602.20667/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2602.20667/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'