Problem 596

Erdős Problem #596: declared status 'open'. Formalized: yes. For which graphs $G_1,G_2$ is it true that {UL} {LI} 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{/LI} {LI} for every graph $H$ without a $G_1$ there is an $\aleph_0$-colouring of the edges of $H$ without a monochromatic $G_2$. {/UL} Prize: no. Tags: graph theory, ramsey theory, set theory.