The Erdos-Gyarfas function with respect to Gallai-colorings

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 Erdos and Gyarfas in 1997, and is now known as the Erdos-Gyarfas 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 <= q <= 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 >= 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 is an element of{1,2}, g is at most a fractional power of n when q = [root p-1], and g is logarithmic in n when 2 <= q <= [log(2)(p-1)] + 1.