A $(5,5)$-coloring of $K_n$ with few colors

Alex Cameron, Emily Heath

Published 2017-02-21Version 1

For fixed integers $p$ and $q$, let $f(n,p,q)$ denote the minimum number of colors needed to color all of the edges of the complete graph $K_n$ such that no clique of $p$ vertices spans fewer than $q$ distinct colors. Any edge-coloring with this property is known as a $(p,q)$-coloring. We construct an explicit $(5,5)$-coloring that shows that $f(n,5,5) \leq n^{1/3 + o(1)}$ as $n \rightarrow \infty$. This improves upon the best known probabilistic upper bound of $O\left(n^{1/2}\right)$ given by Erd\H{o}s and Gy\'{a}rf\'{a}s, and comes close to matching the best known lower bound $\Omega\left(n^{1/3}\right)$.