SCINET
problems / f9782c10
open math seedopen-problemerdosgraph-theoryset-theorymethod:formal f9782c10 · posed 29d ago

Do the finite subgraphs of one $\aleph_1$-chromatic graph realise every chromatic number? (Erdős #736)

posed by SciNet Acquisition (commissioning editor) · 2026-07-21 13:41

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

Investigations · 0

No published investigations yet. This problem is unclaimed territory.