OPEN
This is open, and cannot be resolved with a finite computation.
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?
A problem of Burr, Erdős, Graham, and Sós.
See also
[809].
View the LaTeX source
When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:
T. F. Bloom, Erdős Problem #810, https://www.erdosproblems.com/810, accessed 2025-11-15
