Do the finite subgraphs of one $\aleph_1$-chromatic graph realise every chromatic number? (Erdős #736)
Statement
Let $G$ be a graph with chromatic number $\aleph_1$. Is it true that for every cardinal $m$ there exists a graph $G_m$ of chromatic number $m$ such that every finite subgraph of $G_m$ is isomorphic to a subgraph of $G$? In words: do the finite subgraphs of a single $\aleph_1$-chromatic graph already suffice to build graphs of arbitrarily large chromatic number? More generally, replace $\aleph_1$ by an arbitrary uncountable cardinal $\kappa$. (Erdős further asks to characterise the families $\mathcal{F}_\alpha$ of finite graphs for which some graph of chromatic number $\aleph_\alpha$ has all of its finite subgraphs in $\mathcal{F}_\alpha$.)
Acceptance. FULLY RESOLVES: a complete proof — machine-checkable (Lean/Coq) preferred, else fully written — either establishing Taylor's conjecture in ZFC (for every $\aleph_1$-chromatic $G$ and every cardinal $m$, a graph $G_m$ of chromatic number $m$ with all finite subgraphs embedding into $G$ exists), or refuting it in ZFC, or proving it independent by exhibiting a model where it holds to complement the Komjáth–Shelah model where it fails. ADVANCES (each checkable): improve the Komjáth–Shelah consistency result — they force a $G$ for which the finite-subgraph closure caps chromatic number at $\aleph_2$; stated in words, that cap is $\aleph_2$, so force a strictly smaller cap (e.g. $\aleph_1$) with proof; OR settle the conjecture under a specific axiom such as CH, GCH, or $V=L$; OR resolve the uncountable-$\kappa$ generalization for a specific $\kappa$; OR deliver a Lean/Coq formalization of the KoSh05 construction. Deliver the forcing/model construction or the proof object.
Background
A conjecture of Walter Taylor, recorded by Erdős as [Er81] and [Er93,p.343]; listed as open on erdosproblems.com/736 (fetched 2026-07-21, status 'not provable'). The certificate class NOT PROVABLE reflects a consistency result of Komjáth and Shelah [KoSh05]: it is consistent with ZFC that the answer is NO — there is a graph $G$ with $\chi(G)=\aleph_1$ such that every graph $H$ all of whose finite subgraphs embed into $G$ has $\chi(H)\le\aleph_2$, capping the attainable chromatic numbers well below 'arbitrarily large'. Whether Taylor's conjecture holds in ZFC, fails in ZFC, or is independent remains open. It sits among several infinite-chromatic-number problems already on the venue — e.g. Erdős #918 (erdosproblems.com/918, a graph of chromatic number $\aleph_2$ whose $\aleph_1$-vertex subgraphs are countably chromatic) and Erdős #75 (erdosproblems.com/75) — but is distinct from each. No cash prize was attached. Attacker's tool: forcing and inner-model consistency methods to pin down the status of the conjecture, or a machine-checked (Lean/Coq) formalization of the Komjáth–Shelah construction.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #736 (T. F. Bloom) | website |
| REF-02 | Erdős Problem #918 — infinite chromatic number (venue neighbour) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.