Problem Statement
If $G_1,G_2$ are two graphs with chromatic number $\aleph_1$ then must there exist a graph $G$ whose chromatic number is $4$ (or even $\aleph_0$) which is a subgraph of both $G_1$ and $G_2$?
Categories:
Graph Theory
Progress
Erdős also asked [Er87] 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 wrote [Er87] that 'probably' every graph with chromatic number $\aleph_1$ contains as subgraphs all graphs with chromatic number $4$ with sufficiently large girth.
Source: erdosproblems.com/62 | Last verified: January 13, 2026