Hostname: page-component-7c8c6479df-hgkh8 Total loading time: 0 Render date: 2024-03-27T11:27:09.376Z Has data issue: false hasContentIssue false

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

Published online by Cambridge University Press:  01 July 2008

PETER ALLEN*
Affiliation:
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.

Type
Paper
Copyright
Copyright © Cambridge University Press 2008

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Erdős, P., Gyárfás, A. and Pyber, L. (1991) Vertex coverings by monochromatic cycles and trees. J. Combin. Theory Ser. B 51 9095.Google Scholar
[2]Erdős,, P. and Szekeres, G. (1935) A combinatorial problem in geometry. Compos. Math. 2 464470.Google Scholar
[3]Gyárfás, A. (1983) Vertex coverings by monochromatic paths and cycles. J. Graph Theory 7 131135.Google Scholar
[4]Gyárfás, A., Ruszinkó, M.Sárközy, G. N. and Szemerédi, E. (2006) An improved bound for the monochromatic cycle partition number. J. Combin. Theory Ser. B 96 855873.Google Scholar
[5]Komlós, J., Sárközy, G. N. and Szemerédi, E. (1997) Blow-up lemma. Combinatorica 17 109123.Google Scholar
[6]Lehel, J. Private communication.Google Scholar
[7]Łuczak, T., Rödl, V. and Szemerédi, E. (1998) Partitioning two-coloured complete graphs into two monochromatic cycles. Combin. Probab. Comput. 7 423436.Google Scholar
[8]Szemerédi, E. (1976) Regular partitions of graphs. In Problèmes Combinatoires et Théorie des Graphes, Vol. 260 of Colloques Internationaux CNRS, pp. 399401.Google Scholar