Centre for Discrete and Applicable Mathematics 

CDAM Research Report, LSECDAM200702January 2007 
Asymmetric Ramsey Properties of Random Graphs Involving Cliques
M. Marciniszyn, J. Skokan, R. Spöhel, A. Steger
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 Rucinski 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 thatIn this paper 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 kedgecoloring of G_{n, p} with
A PDF file (424 kB) with the full contents of this report can be downloaded by clicking here.
Alternatively, if you would like to get a free hard copy of this report, please send the number of this report, LSECDAM200702, together with your name and postal address to:
CDAM Research Reports Series Centre for Discrete and Applicable Mathematics London School of Economics Houghton Street London WC2A 2AE, U.K. 

Phone: +44(0)207955 7494. Fax: +44(0)207955 6877. Email: info@maths.lse.ac.uk 
Introduction to the CDAM Research Report Series.  
CDAM Homepage. 