Problem 739

Let $\mathfrak{m}$ be an infinite cardinal and $G$ be a graph with chromatic number $\mathfrak{m}$ . Is it true that, for every infinite cardinal $\mathfrak{n}< \mathfrak{m}$ , there exists a subgraph of $G$ with chromatic number $\mathfrak{n}$ ?

Source: erdosproblems.com/739

Graph theory
Chromatic number

Wiki page

Status

Open

No claim settles this problem.

Open. The site labels the problem NOT PROVABLE, on the strength of Komjáth's consistency result: in a model of ZFC there is a graph of chromatic number $\aleph_2$ with no subgraph of chromatic number $\aleph_1$ , so ZFC does not prove the statement. That settles one side only. Whether the statement is also not disprovable, for instance whether it follows from the Generalized Continuum Hypothesis, is open, and the page departs from the site's label because one side alone leaves the question open.

Problem 739

Status

Proof claims

Discussion