OPEN

Show that
\[R(3,k+1)-R(3,k)\to\infty\]
as $k\to \infty$. Similarly, prove or disprove that
\[R(3,k+1)-R(3,k)=o(k).\]

See also [165] and the entry in the graphs problem collection.

OPEN

Let $R(G;k)$ denote the minimal $m$ such that if the edges of $K_m$ are $k$-coloured then there is a monochromatic copy of $G$. Show that
\[\lim_{k\to \infty}\frac{R(C_{2n+1};k)}{R(K_3;k)}=0\]
for any $n\geq 2$.

A problem of Erdős and Graham. The problem is open even for $n=2$.

OPEN

Let $R(G;k)$ denote the minimal $m$ such that if the edges of $K_m$ are $k$-coloured then there is a monochromatic copy of $G$. Determine the value of
\[R(C_{2n};k).\]

SOLVED

Let $R(G;3)$ denote the minimal $m$ such that if the edges of $K_m$ are $3$-coloured then there must be a monochromatic copy of $G$. Show that
\[R(C_n;3) \leq 4n-3.\]

A problem of Bondy and Erdős. This inequality is best possible for odd $n$.

Luczak [Lu99] has shown that $R(C_n;3)\leq (4+o(1))n$ for all $n$, and in fact $R(C_n;3)\leq 3n+o(n)$ for even $n$.

Kohayakawa, Simonovits, and Skokan [KSS05] proved this conjecture when $n$ is sufficiently large and odd. Benevides and Skokan [BeSk09] proved that if $n$ is sufficiently large and even then $R(C_n;3)=2n$.

OPEN

Let $R(G;k)$ denote the minimal $m$ such that if the edges of $K_m$ are $k$-coloured then there is a monochromatic copy of $G$. Is it true that
\[R(T;k)=kn+O(1)\]
for any tree $T$ on $n$ vertices?

A problem of Erdős and Graham. Implied by [548].

OPEN

Let $R(G;k)$ denote the minimal $m$ such that if the edges of $K_m$ are $k$-coloured then there is a monochromatic copy of $G$. Determine
\[R(K_{s,t};k)\]
where $K_{s,t}$ is the complete bipartite graph with $s$ vertices in one component and $t$ in the other.

Chung and Graham [ChGr75] prove the bounds
\[(2\pi\sqrt{st})^{\frac{1}{s+t}}\left(\frac{s+t}{e^2}\right)k^{\frac{st-1}{s+t}}\leq R(K_{s,t};k)\leq (t-1)(k+k^{1/s})^s.\]
For example this implies that
\[R(K_{3,3};k) \ll k^3.\]
Using Turán numbers one can show that
\[R(K_{3,3};k) \gg \frac{k^3}{(\log k)^3}.\]