Logo
All Random Solved Random Open
OPEN
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$?
Erdős, Hajnal, and Shelah have shown that $G_1$ and $G_2$ must both contain all sufficiently large cycles.