Hostname: page-component-586b7cd67f-t7fkt Total loading time: 0 Render date: 2024-11-24T23:00:00.806Z Has data issue: false hasContentIssue false
  • English
  • Français

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

Published online by Cambridge University Press:  01 July 2008

PETER ALLEN
PETER ALLEN*
Affiliation:
Department of Mathematics, London School of Economics, Houghton Street, London WC2A 2AE, UK (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

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 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.

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 17 , Issue 4 , July 2008 , pp. 471 - 486
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 90–95.CrossRefGoogle Scholar
[2]Erdős,, P. and Szekeres, G. (1935) A combinatorial problem in geometry. Compos. Math. 2 464–470.Google Scholar
[3]Gyárfás, A. (1983) Vertex coverings by monochromatic paths and cycles. J. Graph Theory 7 131–135.CrossRefGoogle 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 855–873.CrossRefGoogle Scholar
[5]Komlós, J., Sárközy, G. N. and Szemerédi, E. (1997) Blow-up lemma. Combinatorica 17 109–123.CrossRefGoogle 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 423–436.CrossRefGoogle 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. 399–401.Google Scholar