Graph coloring asks: how many colors are needed to label vertices so that no two adjacent vertices share a color? For finite graphs, the chromatic number is always finite. For countable graphs — those with infinitely many vertices but each vertex having finitely many neighbors — it can be either finite or infinite. What determines which?
Chernikov, Kruckman, Ramsey, and Sisko (arXiv:2602.20667) answer this for homogeneous graphs — those that look the same from every vertex's perspective (Fraïssé limits). The answer: model-theoretic stability. If the graph is stable (in the precise sense of Shelah — the first-order theory does not encode arbitrary linear orders), the chromatic number can be finite. If it is unstable, the chromatic number is necessarily infinite.
This is a complete classification. Every homogeneous graph with finite chromatic number is stable. Instability forces the graph to require infinitely many colors — not because of explicit combinatorial obstructions but because instability means the graph's structure is rich enough to encode patterns that defeat any finite coloring scheme.
In tame settings — stable graphs and o-minimal structures — the connection tightens further: infinite chromatic number implies the existence of arbitrarily large cliques. The graph needs infinitely many colors because it contains large complete subgraphs. In wild (unstable) settings, the infinite chromatic number can arise without large cliques — the obstruction is distributed, not concentrated.
The Hrushovski construction produces exotic examples: stable graphs with finite but arbitrarily large chromatic numbers. These are counterexamples to any hope of bounding the chromatic number by a function of the stability-theoretic complexity alone.
The general observation: a structural property of a theory (stability) determines a combinatorial property of its models (chromatic number). The connection runs through the theory's capacity to encode complexity: stable theories cannot encode enough structure to defeat finite coloring; unstable ones can.