OPEN
This is open, and cannot be resolved with a finite computation.
Is there a graph with $\aleph_2$ vertices and chromatic number $\aleph_2$ such that every subgraph on $\aleph_1$ vertices has chromatic number $\leq\aleph_0$?
Is there a graph with $\aleph_{\omega+1}$ vertices and chromatic number $\aleph_1$ such that every subgraph on $\aleph_\omega$ vertices has chromatic number $\leq\aleph_0$?
A question of Erdős and Hajnal
[ErHa68b], who proved that for every finite $k$ there is a graph with chromatic number $\aleph_1$ where each subgraph on less than $\aleph_k$ vertices has chromatic number $\leq \aleph_0$.
In
[Er69b] it is asked with chromatic number $=\aleph_0$, but in the comments louisd observes this is (assuming subgraph and not induced subgraph was intended) trivially impossible, and hence presumably the problem was intended as written here (which is how it is posed in
[ErHa68b]).
View the LaTeX source
This page was last edited 24 October 2025.
Additional thanks to: louisd and Salvatore Mercuri
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 #918, https://www.erdosproblems.com/918, accessed 2025-11-15
