An application of the regularity lemma in generalized Ramsey theory |
| |
Authors: | G bor N. S rk zy,Stanley M. Selkow |
| |
Affiliation: | Gábor N. Sárközy,Stanley M. Selkow |
| |
Abstract: | Given graphs G and H, an edge coloring of G is called an (H,q)‐coloring if the edges of every copy of H ? 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 Erd?s and Gyárfás studied r(Kn,Kp,q) if p and q are fixed and n tends to infinity. They determined for every fixed p the smallest q (denoted by qlin) for which r(Kn,Kp,q) is linear in n and the smallest q (denoted by qquad) for which r(Kn,Kp,q) is quadratic in n. They raised the problem of determining the smallest q for which we have . In this paper by using the Regularity Lemma we show that if , then we have . © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 39–49, 2003 |
| |
Keywords: | regularity lemma generalized Ramsey theory |
|
|