Logo
All Random Solved Random Open
OPEN
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?
Conjectured by Erdős, Hajnal, and Szemerédi [EHS82]. This fails if the graph has chromatic number $\aleph_0$.