An application of the regularity lemma in generalized Ramsey theory

✍ Scribed by Gábor N. Sárközy; Stanley M. Selkow

• Publisher: John Wiley and Sons
• Year: 2003
• Tongue: English
• Weight: 116 KB
• Volume: 44
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.10129

✦ Synopsis

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(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) = \left( {\matrix{n \cr 2 \cr } } \right) - 0(n^2 )$. In this paper by using the Regularity Lemma we show that if $q > q_{quad} + \left\lceil {{{\log _2 p} \over 2}} \right\rceil $, then we have $r(K_{n,} K_{p,} q) = \left( {\matrix{ n \cr 2 \cr } } \right) - 0(n^2 )$. © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 39–49, 2003