The Library
Covering two-edge-coloured complete graphs with two disjoint monochromatic cycles
Tools
Allen, Peter (2008) Covering two-edge-coloured complete graphs with two disjoint monochromatic cycles. Combinatorics, Probability and Computing, Vol.17 (No.4). pp. 471-486. doi:10.1017/S0963548308009164 ISSN 0963-5483.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1017/S0963548308009164
Abstract
n 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.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||
Journal or Publication Title: | Combinatorics, Probability and Computing | ||||
Publisher: | Cambridge University Press | ||||
ISSN: | 0963-5483 | ||||
Official Date: | 2008 | ||||
Dates: |
|
||||
Volume: | Vol.17 | ||||
Number: | No.4 | ||||
Page Range: | pp. 471-486 | ||||
DOI: | 10.1017/S0963548308009164 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |