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.
View the LaTeX source
This page was last edited 01 October 2025. View history
When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:
T. F. Bloom, Erdős Problem #110, https://www.erdosproblems.com/110, accessed 2026-04-11
