SOLVED
This has been resolved in some other way than a proof or disproof.
Let $f(n)$ be the smallest number of colours required to colour the edges of $K_n$ such that every $K_4$ contains at least 5 colours. Determine the size of $f(n)$.
Asked by Erdős and Gyárfás, who proved that\[\frac{5}{6}(n-1) < f(n)<n,\]and that $f(9)=8$. Erdős believed the upper bound is closer to the truth. In fact the lower bound is: Bennett, Cushman, Dudek,and Pralat
[BCDP22] have shown that\[f(n) \sim \frac{5}{6}n.\]Joos and Mubayi
[JoMu22] have found a shorter proof of this.
See also
[135].
View the LaTeX source
View history
|
Likes this problem
|
None
|
|
Interested in collaborating
|
None
|
|
Currently working on this problem
|
None
|
|
This problem looks difficult
|
None
|
|
This problem looks tractable
|
None
|
|
The results on this problem could be formalisable
|
None
|
|
I am working on formalising the results on this problem
|
None
|
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 #136, https://www.erdosproblems.com/136, accessed 2026-04-11
