Problem Statement
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$?
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$?
Categories:
Graph Theory Chromatic Number
Progress
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]).
Source: erdosproblems.com/918 | Last verified: January 19, 2026