Logo
All Random Solved Random Open
OPEN
Let $G_1$ and $G_2$ be two graphs with chromatic number $\aleph_1$. Must there be a graph $H$ with chromatic number $4$ which appears as a subgraph of both $G_1$ and $G_2$? Is there such an $H$ with chromatic number $\aleph_0$?
Erdős also asks about finding a common subgraph $H$ (with chromatic number either $4$ or $\aleph_0$) in any finite collection of graphs with chromatic number $\aleph_1$.

Every graph with chromatic number $\aleph_1$ contains all sufficiently large odd cycles (which have chromatic number $3$), see [594]. This was proved by Erdős, Hajnal, and Shelah [EHS74]. Erdős writes that 'probably' every graph with chromatic number $\aleph_1$ contains as subgraphs all graphs with chromatic number $4$ with sufficiently large girth.