Submission date: 10 August 2024

Abstract:

Suppose that G is a graph of cardinality μ^+ with chromatic number χ(G) ≥ μ^+. One possible reason that this could happen is if G contains a clique of size μ^+. 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.

Mathematics Subject Classification:

Keywords and phrases:

Full text arXiv 2408.05605: pdf, ps.