CDAM: Computational, Discrete and Applicable
Mathematics@LSE


CDAM Research Report, LSECDAM200718July 2007 
Covering twoedgecoloured complete graphs with two disjoint monochromatic cycles
Peter Allen
In 1998 Łuczak, Rödl and Szemerédi proved, by means of the Regularity Lemma, that there exists n_{0} such that, for any n ≥ n_{0} and twoedgecolouring of K_{n}, there exists a pair of vertex disjoint monochromatic cycles of opposite colours covering the vertices of K_{n}. In this paper we make use of an alternative method of finding useful structure in a graph, leading to a proof of the same result with a much smaller value of n_{0}. The proof gives a polynomial time algorithm for finding the two cycles.A PDF file (172 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, LSECDAM200718, 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@LSE Homepage. 