Infinite stable graphs with large chromatic number II

Abstract

We prove a version of the strong Taylor’s conjecture for stable graphs: if $G$ is a stable graph whose chromatic number is strictly greater than ${\beth }_2({\aleph }_0)$ then $G$ contains all finite subgraphs of ${\text{Sh}}_n(\omega )$ and thus has elementary extensions of unbounded chromatic number. This completes the picture from our previous work. The main new model-theoretic ingredient is a generalization of the classical construction of Ehrenfeucht–Mostowski models to an infinitary setting, giving a new characterization of stability.