Premium
Asymmetric Ramsey properties of random graphs involving cliques
Author(s) -
Marciniszyn Martin,
Skokan Jozef,
Spöhel Reto,
Steger Angelika
Publication year - 2009
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20239
Subject(s) - combinatorics , conjecture , mathematics , constant (computer programming) , graph , edge coloring , graph coloring , function (biology) , discrete mathematics , graph power , computer science , line graph , evolutionary biology , programming language , biology
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