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 ErdH{o}s and Gy{a}rf{a}s in 1997, and is now known as the ErdH{o}s-Gy{a}rf{a}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 $2leq qleq 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 $pgeq 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 $cin {1,2}$, $g$ is at most a fractional power of $n$ when $q=lfloorsqrt{p-1}rfloor$, and $g$ is logarithmic in $n$ when $2leq qleq lfloorlog_2 (p-1)rfloor+1$.
تحميل البحث