Problem Statement
Let $G$ be a graph with chromatic number $\aleph_1$. Is there, for every cardinal number $m$, some graph $G_m$ of chromatic number $m$ such that every finite subgraph of $G_m$ is a subgraph of $G$?
Categories:
Graph Theory Chromatic Number
Progress
A conjecture of Walter Taylor. The more general problem replaces $\aleph_1$ with any uncountable cardinal $\kappa$.More generally, Erdős asks to characterise families $\mathcal{F}_\alpha$ of finite graphs such that there is a graph of chromatic number $\aleph_\alpha$ all of whose finite subgraphs are in $\mathcal{F}_\alpha$.
Komjáth [KoSh05] proved that it is consistent that the answer is no, in that there exists a graph $G$ with chromatic number $\aleph_1$ such that if $H$ is any graph all of whose finite subgraphs are subgraphs of $G$ then $H$ has chromatic number $\leq \aleph_2$.
Source: erdosproblems.com/736 | Last verified: January 16, 2026