Infinite Stable Graphs With Large Chromatic Number

Abstract

We prove that if $G=(V,E)$ is an $\omega$-stable (respectively, superstable) graph with $\chi (G)>{\aleph }_0$ (respectively, $2^{{\aleph }_0}$) then $G$ contains all the finite subgraphs of the shift graph ${\text{Sh}}_n(\omega )$ for some $n$. We prove a variant of this theorem for graphs interpretable in stationary stable theories. Furthermore, if $G$ is $\omega$-stable with $\mathrm{U}(G)\le 2$ we prove that $n\le 2$ suffices.