Problem Statement
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)$.
Categories:
Graph Theory
Progress
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].
Source: erdosproblems.com/136 | Last verified: January 13, 2026