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

Alex Cameron¹

¹University of Illinois at Chicago

The electronic journal of combinatorics, Tome 26 (2019) no. 4

Résumé

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)=O\left(n^{3/5}\right)$ 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) = \Omega\left(n^{1/2}\right)$.

Détail

DOI : 10.37236/7852

Classification : 05C55, 05D10, 05C15
Mots-clés : extremal graph theory, probabilistic methods