Infinite Stable Graphs With Large Chromatic Number

DOI10.1090/TRAN/8570arXiv2007.12139MaRDI QIDQ6345716

Itay Kaplan, Yatir Halevi, Saharon Shelah

Publication date: 23 July 2020

Abstract: We prove that if $G=(V,E)$ is an $omega$-stable (respectively, superstable) graph with $chi(G)>alep{h}_0$ (respectively, $2^{alep{h}_0}$) then $G$ contains all the finite subgraphs of the shift graph $ext{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 $mathrmU(G)leq2$ we prove that $nleq2$ suffices.

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Classification theory, stability, and related concepts in model theory (03C45)

This page was built for publication: Infinite Stable Graphs With Large Chromatic Number

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6345716)