Hostname: page-component-74656f9884-g96k6 Total loading time: 0 Render date: 2026-11-10T04:01:55.842Z 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: p.d.allen@lse.ac.uk)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 17 , Issue 4 , July 2008 , pp. 471 - 486
Copyright
Copyright © Cambridge University Press 2008

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