Problem Statement
For which graphs $G_1,G_2$ is it true that
- for every $n\geq 1$ there is a graph $H$ without a $G_1$ but if the edges of $H$ are $n$-coloured then there is a monochromatic copy of $G_2$, and yet
- for every graph $H$ without a $G_1$ there is an $\aleph_0$-colouring of the edges of $H$ without a monochromatic $G_2$.
Categories:
Graph Theory Ramsey Theory Set Theory
Progress
Erdős and Hajnal originally conjectured that there are no such $G_1,G_2$, but in fact $G_1=C_4$ and $G_2=C_6$ is an example. Indeed, for this pair Nešetřil and Rödl established the first property and Erdős and Hajnal the second (in fact every $C_4$-free graph is a countable union of trees).Whether this is true for $G_1=K_4$ and $G_2=K_3$ is the content of [595].
Source: erdosproblems.com/596 | Last verified: January 15, 2026