Problem 918

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

Source: erdosproblems.com/918

Graph theory
Chromatic number

Wiki page

Status

Open

No claim settles this problem.

Open. The first question (the part q1) is independent of ZFC + GCH, relative to a huge cardinal: Baumgartner 1984 settles its not disprovable side and Foreman and Laver 1988 its not provable side. The second question (the part q2) is open: Rinot 2015 settles its not disprovable side, and one side alone leaves the question open. The site labels the problem OPEN.

Problem 918

Status

Proof claims

Discussion