OPENHARDgraph theoryset theory
If $G_1,G_2$ are two graphs with chromatic number $\aleph_1$ then must there exist a graph $G$ with chromatic number $4$ (or even $\aleph_0$) which is a subgraph of both?
Notes: Every graph with chromatic number aleph_1 contains all sufficiently large odd cycles (Erdos-Hajnal-Shelah). Erdos conjectured every such graph contains all 4-chromatic graphs of sufficiently large girth.
AI Status: NONE · 0 total attempts