Problem 810

Erdős Problem #810: declared status 'open'. Formalized: no. Does there exist some $\epsilon>0$ such that, for all sufficiently large $n$, there exists a graph $G$ on $n$ vertices with at least $\epsilon n^2$ many edges such that the edges can be coloured with $n$ colours so that every $C_4$ receives $4$ distinct colours? Prize: no. Tags: graph theory, ramsey theory.