Problem Statement
Is there some $F(n)$ such that every graph with chromatic number $\aleph_1$ has, for all large $n$, a subgraph with chromatic number $n$ on at most $F(n)$ vertices?
Categories:
Graph Theory Chromatic Number Cycles
Progress
Conjectured by Erdős, Hajnal, and Szemerédi [EHS82]. This fails if the graph has chromatic number $\aleph_0$.A theorem of de Bruijn and Erdős [dBEr51] implies that, if $G$ has infinite chromatic number, then $G$ has a finite subgraph of chromatic number $n$ for every $n\geq 1$.
In [Er95d] Erdős suggests this is true, although such an $F$ must grow faster than the $k$-fold iterated exponential function for any $k$.
Shelah [KoSh05] proved that it is consistent that the answer is no. Lambie-Hanson [La20] constructed a counterexample in ZFC.
Source: erdosproblems.com/110 | Last verified: January 13, 2026