Does chromatic number $\mathfrak{m}$ force a subgraph of every smaller infinite chromatic number? (Erdős #739)
Statement
Let $\mathfrak{m}$ be an infinite cardinal and let $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$ whose chromatic number is exactly $\mathfrak{n}$? (The stronger variant asks for an induced subgraph of chromatic number $\mathfrak{n}$.)
Acceptance. FULLY RESOLVES: a complete proof — machine-checkable (Lean/Coq) preferred, else fully written — either that every graph of chromatic number $\mathfrak{m}$ has, for each infinite $\mathfrak{n}<\mathfrak{m}$, a subgraph of chromatic number exactly $\mathfrak{n}$ (in ZFC), or a ZFC counterexample, or a proof of independence complementing Komjáth's consistency of failure and Shelah's $V=L$ positive result. ADVANCES (each checkable): decide the currently open case under GCH — either prove 'yes under GCH' or force a GCH model with a counterexample; OR extend Galvin's $\mathfrak{m}=\aleph_0$ theorem to a new value of $\mathfrak{m}$ in ZFC; OR weaken Shelah's $V=L$ hypothesis for the $(\aleph_2,\aleph_1)$ case; OR deliver a Lean/Coq formalization of Galvin's or Shelah's proof. Deliver the forcing/model construction or the proof object.
Background
A question of Galvin [Ga73], recorded by Erdős as [Er81]; listed as open on erdosproblems.com/739 (fetched 2026-07-21, status 'not provable'). Galvin proved the statement when $\mathfrak{m}=\aleph_0$, and showed that the stronger induced-subgraph version implies $2^{\mathfrak{k}}<2^{\mathfrak{n}}$ for all infinite $\mathfrak{k}<\mathfrak{n}$. The certificate class NOT PROVABLE reflects a consistency result of Komjáth [Ko88b]: it is consistent that $2^{\aleph_0}=2^{\aleph_1}=2^{\aleph_2}=\aleph_3$ and that there is a graph failing the property with $\mathfrak{m}=\aleph_2$, $\mathfrak{n}=\aleph_1$. In the other direction, Shelah [Sh90] proved that under the axiom of constructibility ($V=L$) the answer is yes for $\mathfrak{m}=\aleph_2$, $\mathfrak{n}=\aleph_1$. It remains open whether the answer is yes under, for example, the generalized continuum hypothesis. This is a companion to Taylor's conjecture, Erdős #736 (erdosproblems.com/736), also on the venue. No cash prize was attached. Attacker's tool: forcing and inner-model ($V=L$) consistency arguments, or a machine-checked (Lean/Coq) formalization of Galvin's or Shelah's proof.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #739 (T. F. Bloom) | website |
| REF-02 | Erdős Problem #736 — Taylor's conjecture (companion, venue neighbour) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.