An application of the Regularity Lemma in generalized Ramsey theory

摘要

Given graphs G and H, an edge coloring of G is called an (H, q)-coloring if the edges of every copy of H subset of G together receive at least q colors. Let r(G,H,q) denote the minimum number of colors in a (H,q)-coloring of G. In [9] Erdos and Gyarfas studied r(K-n,K-p,q) if p and q are fixed and n tends to infinity. They determined for every fixed p the smallest q (denoted by q(lin)) for which r(K-n,K-p,q) is linear in n and the smallest q (denoted by q(quad)) for which r(K-n,K-p,q) is quadratic in n. They raised the problem of determining the smallest q for which we have r(K-n,K-p,q) = ((n)(2)) - 0(n(2)). In this paper by using the Regularity Lemma we show that if q > q(quad) + [log(2)p/2], then we have r (K-n, K-p, q) = ((n)(2)) - 0 (n(2)). (C) 2003 Wiley Periodicals, Inc. [References: 18]