Erdős Problems

Tags Prizes

OPEN

For which graphs $G$ does the following hold: for all large $n$ there exists some $d_G(n)$ such that if $n$ is sufficiently large and the edges of $K_n$ are coloured with $e(G)$ many colours such that the minimum degree of each colour class is $\geq d_G(n)$ then there is a subgraph isomorphic to $G$ where each edge receives a different colour?

If $d_G(n)$ exists then determine the best possible value of $d_G(n)$.

#811: [Er91]

graph theory, ramsey theory

A problem of Erdős, Pyber, and Tuza, who observe that if $d_G(n)$ exists then $d_G(n) < \frac{n-1}{e(G)}$.

The Kürschák competition in Hungary in 1986 asked students to prove that $d_{K_3}(n)$ exists. Kostochka proved that $d_{K_3}(n)=n/4$ is the best possible. Tuza proved that \[d_{C_4}(n) \leq \left(\frac{1}{4}-c\right)n\] for some constant $c>0$. Brightwell and Trotter proved that \[d_{C_6}(n) > (1-o(1))\frac{n}{6}.\]