An Explicit Edge-Coloring of $K_n$ with Six Colors on Every $K_5$

摘要

Let $p$ and $q$ be positive integers such that $1 leq q leq {p choose 2}$. A $(p,q)$-coloring of the complete graph on $n$ vertices $K_n$ is an edge coloring for which every $p$-clique contains edges of at least $q$ distinct colors. We denote the minimum number of colors needed for such a $(p,q)$-coloring of $K_n$ by $f(n,p,q)$. This is known as the Erd?s-Gyárfás function. In this paper we give an explicit $(5,6)$-coloring with $n^{1/2+o(1)}$ colors. This improves the best known upper bound of $f(n,5,6)=Oleft(n^{3/5}ight)$ given by Erd?s and Gyárfás, and comes close to matching the order of the best known lower bound, $f(n,5,6) = Omegaleft(n^{1/2}ight)$.