An explicit edge-coloring of \(K_n\) with six colors on every \(K_5\) (Q2327227)

Summary: Let \(p\) and \(q\) be positive integers such that \(1 \leq q \leq \binom{p}{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)=O\left(n^{3/5}\right)\) given by \textit{P. Erdős} and \textit{A. Gyárfás} [Combinatorica 17, No. 4, 459--467 (1997; Zbl 0910.05034)], and comes close to matching the order of the best known lower bound, \(f(n,5,6) = \Omega\left(n^{1/2}\right)\).