Abstract

Suppose that $G$ is a graph of cardinality ${\mu }^{+}$ with chromatic number $\chi (G)\ge {\mu }^{+}$. One possible reason that this could happen is if $G$ contains a clique of size ${\mu }^{+}$. We prove that this is indeed the case when the edge relation is stable. When $G$ is a random graph (which is simple but not stable), this is not true. But still if in general the complete theory of $G$ is simple, $G$ must contain finite cliques of unbounded sizes.

Keywords

Mathematical Subject Classification

Milestones

Authors