Combinatorics, Probability and Computing

Paper

Covering Two-Edge-Coloured Complete Graphs with Two Disjoint Monochromatic Cycles

PETER ALLENa1

a1 Department of Mathematics, London School of Economics, Houghton Street, London WC2A 2AE, UK (e-mail: p.d.allen@lse.ac.uk)

Abstract

In 1998 Łuczak Rödl and Szemerédi [7] proved, by means of the Regularity Lemma, that there exists n0 such that, for any nn0 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.

(Received July 18 2007)

(Revised April 02 2008)

(Online publication June 13 2008)