{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,19]],"date-time":"2026-01-19T23:37:20Z","timestamp":1768865840567,"version":"3.49.0"},"reference-count":8,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2008,7,1]],"date-time":"2008-07-01T00:00:00Z","timestamp":1214870400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2008,7]]},"abstract":"<jats:p>In 1998 \u0141uczak R\u00f6dl and Szemer\u00e9di [7] proved, by means of the Regularity Lemma, that there exists <jats:italic>n<\/jats:italic><jats:sub>0<\/jats:sub> such that, for any <jats:italic>n<\/jats:italic> \u2265 <jats:italic>n<\/jats:italic><jats:sub>0<\/jats:sub> and two-edge-colouring of <jats:italic>K<\/jats:italic><jats:sub>n<\/jats:sub>, there exists a pair of vertex-disjoint monochromatic cycles of opposite colours covering the vertices of <jats:italic>K<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic><\/jats:sub>. 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 <jats:italic>n<\/jats:italic><jats:sub>0<\/jats:sub>. The proof gives a polynomial-time algorithm for finding the two cycles.<\/jats:p>","DOI":"10.1017\/s0963548308009164","type":"journal-article","created":{"date-parts":[[2008,6,13]],"date-time":"2008-06-13T05:03:19Z","timestamp":1213333399000},"page":"471-486","source":"Crossref","is-referenced-by-count":42,"title":["Covering Two-Edge-Coloured Complete Graphs with Two Disjoint Monochromatic Cycles"],"prefix":"10.1017","volume":"17","author":[{"given":"PETER","family":"ALLEN","sequence":"first","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2008,7,1]]},"reference":[{"key":"S0963548308009164_ref8","first-page":"399","article-title":"Regular partitions of graphs","volume":"260","author":"Szemer\u00e9di","year":"1976","journal-title":"Probl\u00e8mes Combinatoires et Th\u00e9orie des Graphes"},{"key":"S0963548308009164_ref7","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548398003599"},{"key":"S0963548308009164_ref1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(91)90007-7"},{"key":"S0963548308009164_ref6","unstructured":"[6] Lehel J. Private communication."},{"key":"S0963548308009164_ref4","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2006.02.007"},{"key":"S0963548308009164_ref3","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190070116"},{"key":"S0963548308009164_ref5","doi-asserted-by":"publisher","DOI":"10.1007\/BF01196135"},{"key":"S0963548308009164_ref2","first-page":"464","article-title":"A combinatorial problem in geometry","volume":"2","author":"Erd\u0151s,","year":"1935","journal-title":"Compos. Math."}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548308009164","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,5]],"date-time":"2019-04-05T15:18:58Z","timestamp":1554477538000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548308009164\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,7]]},"references-count":8,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2008,7]]}},"alternative-id":["S0963548308009164"],"URL":"https:\/\/doi.org\/10.1017\/s0963548308009164","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,7]]}}}