Problem Statement
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}$?
Categories:
Graph Theory Chromatic Number
Progress
A question of Galvin [Ga73], who proved that this is true with $\mathfrak{m}=\aleph_0$. Galvin also proved that the stronger version of this statement, in which the subgraph is induced, implies $2^{\mathfrak{k}}<2^{\mathfrak{n}}$ for all cardinals $\mathfrak{k}<\mathfrak{n}$.Komjáth [Ko88b] proved it is consistent that\[2^{\aleph_0}=2^{\aleph_1}=2^{\aleph_2}=\aleph_3\]and that there exist graphs which fail this property (with $\mathfrak{m}=\aleph_2$ and $\mathfrak{n}=\aleph_1$).
Shelah [Sh90] proved that, assuming the axiom of constructibility, the answer is yes with $\mathfrak{m}=\aleph_2$ and $\mathfrak{n}=\aleph_1$.
It remains open whether the answer to this question is yes assuming the Generalized Continuum Hypothesis, for example.
Source: erdosproblems.com/739 | Last verified: January 16, 2026