Erdős Problems

Tags Prizes

OPEN

Is there a graph with $\aleph_2$ vertices and chromatic number $\aleph_2$ such that every subgraph on $\aleph_1$ vertices has chromatic number $\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 $\aleph_0$?

#918: [ErHa68b][Er69b]

graph theory, chromatic number

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$.