The Erdős-Gyárfás function with respect to Gallai-colorings

Abstract

For fixed $p$ and $q$, an edge-coloring of the complete graph $K_n$ is said to be a $(p,q)$-coloring if every $K_p$ receives at least $q$ distinct colors. The function $f(n,p,q)$ is the minimum number of colors needed for $K_n$ to have a $(p,q)$-coloring. This function was introduced about 45 years ago, but was studied systematically by Erdős and Gyárfás in 1997, and is now known as the Erdős-Gyárfás function. In this paper, we study $f(n,p,q)$ with respect to Gallai-colorings, where a Gallai-coloring is an edge-coloring of $K_n$ without rainbow triangles. Combining the two concepts, we consider the function $g(n,p,q)$ that is the minimum number of colors needed for a Gallai-$(p,q)$-coloring of $K_n$. Using the anti-Ramsey number for $K_3$, we have that $g(n,p,q)$ is nontrivial only for $2\le q\le p-1$. We give a general lower bound for this function and we study how this function falls off from being equal to $n-1$ when $q=p-1$ and $p\ge 4$ to being $\Theta (\log n)$ when $q=2$. In particular, for appropriate $p$ and $n$, we prove that $g=n-c$ when $q=p-c$ and $c\in \{1,2\}$, $g$ is at most a fractional power of $n$ when $q=\lfloor \sqrt{p-1}\rfloor$, and $g$ is logarithmic in $n$ when $2\le q\le \lfloor {\log }_2(p-1)\rfloor +1$.

25 pages

References in corpus (1)

• The Erdős-Gyárfás problem on generalized Ramsey numbers