Asymmetric Ramsey properties of random graphs involving cliques

Consider the following problem: For given graphs G and F 1 ,…, F k , find a coloring of the edges of G with k colors such that G does not contain F i in color i . Rödl and Ruciński studied this problem for the random graph G n , p in the symmetric case when k is fixed and F 1 = ··· = F k = F . They proved that such a coloring exists asymptotically almost surely (a.a.s.) provided that p ≤ bn − β for some constants b = b ( F , k ) and β = β ( F ). This result is essentially best possible because for p ≥ B n − β , where B = B ( F , k ) is a large constant, such an edge‐coloring does not exist. Kohayakawa and Kreuter conjectured a threshold function n   − β ( F   1 ,…, F   k )for arbitrary F 1 ,…, F k . In this article we address the case when F 1 ,…, F k are cliques of different sizes and propose an algorithm that a.a.s. finds a valid k ‐edge‐coloring of G n , p with p ≤ b n − β for some constant b = b ( F 1 ,…, F k ), where β = β ( F 1 ,…, F k ) as conjectured. With a few exceptions, this algorithm also works in the general symmetric case. We also show that there exists a constant B = B ( F 1 ,…, F k ) such that for p ≥ B n − β the random graph G n , p a.a.s. does not have a valid k ‐edge‐coloring provided the so‐called KŁR‐conjecture holds. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2009