CDAM: Computational, Discrete and Applicable Mathematics@LSE

 CDAM Research Report, LSE-CDAM-2007-18

July 2007

Covering two-edge-coloured 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 n0 such that, for any n ≥ n0 and two-edge-colouring of Kn, there exists a pair of vertex disjoint monochromatic cycles of opposite colours covering the vertices of Kn. 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 n0. 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, LSE-CDAM-2007-18, 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)-20-7955 7494.
Fax: +44(0)-20-7955 6877.

Introduction to the CDAM Research Report Series.

CDAM@LSE Homepage.

Copyright © London School of Economics & Political Science 2007