  A $(4, 5)$-coloring of $K_n$ is an edge-coloring of $K_n$ where every
$4$-clique spans at least five colors. We show that there exist $(4,
5)$-colorings of $K_n$ using $\frac 56 n + o(n)$ colors. This settles a
disagreement between Erd\H{o}s and Gy\'arf\'as reported in their 1997 paper.
Our construction uses a randomized process which we analyze using the so-called
differential equation method to establish dynamic concentration. In particular,
our coloring process uses random triangle removal, a process first introduced
by Bollob\'as and Erd\H{o}s, and analyzed by Bohman, Frieze and Lubetzky.
