{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,5]],"date-time":"2026-03-05T03:37:50Z","timestamp":1772681870545,"version":"3.50.1"},"reference-count":28,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2020,12,18]],"date-time":"2020-12-18T00:00:00Z","timestamp":1608249600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2021,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Magnant and Martin conjectured that the vertex set of any <jats:italic>d<\/jats:italic>-regular graph <jats:italic>G<\/jats:italic> on <jats:italic>n<\/jats:italic> vertices can be partitioned into <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548320000553_inline2.png\"\/><jats:tex-math>\n$n \/ (d+1)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> paths (there exists a simple construction showing that this bound would be best possible). We prove this conjecture when <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548320000553_inline1.png\"\/><jats:tex-math>\n$d = \\Omega(n)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, improving a result of Han, who showed that in this range almost all vertices of <jats:italic>G<\/jats:italic> can be covered by <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548320000553_inline3.png\"\/><jats:tex-math>\n$n \/ (d+1) + 1$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> vertex-disjoint paths. In fact our proof gives a partition of <jats:italic>V<\/jats:italic>(<jats:italic>G<\/jats:italic>) into cycles. We also show that, if <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548320000553_inline1.png\"\/><jats:tex-math>\n$d = \\Omega(n)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> and <jats:italic>G<\/jats:italic> is bipartite, then <jats:italic>V<\/jats:italic>(<jats:italic>G<\/jats:italic>) can be partitioned into <jats:italic>n<\/jats:italic>\/(2<jats:italic>d<\/jats:italic>) paths (this bound is tight for bipartite graphs).<\/jats:p>","DOI":"10.1017\/s0963548320000553","type":"journal-article","created":{"date-parts":[[2020,12,18]],"date-time":"2020-12-18T12:56:09Z","timestamp":1608296169000},"page":"526-549","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":7,"title":["Cycle partitions of regular graphs"],"prefix":"10.1017","volume":"30","author":[{"given":"Vytautas","family":"Gruslys","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shoham","family":"Letzter","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2020,12,18]]},"reference":[{"key":"S0963548320000553_ref20","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/pdq035"},{"key":"S0963548320000553_ref13","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1994.1067"},{"key":"S0963548320000553_ref11","unstructured":"[11] Hilbig, F. (1986) Kantenstrukturen in nichthamiltonischen Graphen. PhD thesis, Technical University Berlin."},{"key":"S0963548320000553_ref2","volume-title":"Extremal Graph Theory","author":"Bollob\u00e1s","year":"1978"},{"key":"S0963548320000553_ref23","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2009.11.004"},{"key":"S0963548320000553_ref17","doi-asserted-by":"publisher","DOI":"10.1007\/BF01261324"},{"key":"S0963548320000553_ref28","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(92)90712-O"},{"key":"S0963548320000553_ref1","doi-asserted-by":"crossref","unstructured":"[1] Balogh, J. , Mousset, F. and Skokan, J. (2017) An extension of Dirac\u2019s theorem. Electron. J. Combin. 24 #P3.56.","DOI":"10.37236\/5185"},{"key":"S0963548320000553_ref27","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0059438"},{"key":"S0963548320000553_ref25","doi-asserted-by":"publisher","DOI":"10.37236\/7418"},{"key":"S0963548320000553_ref4","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0118(199606)22:2<105::AID-JGT2>3.0.CO;2-R"},{"key":"S0963548320000553_ref18","doi-asserted-by":"crossref","unstructured":"[18] K\u00fchn, D. , Lo, A. , Osthus, D. and Staden, K. (2015) The robust component structure of dense regular graphs and applications. Proc. London Math. Soc. 110 19\u201356.","DOI":"10.1112\/plms\/pdu039"},{"key":"S0963548320000553_ref5","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2016.08.006"},{"key":"S0963548320000553_ref8","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(85)90058-9"},{"key":"S0963548320000553_ref15","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-444-86893-0.50032-2"},{"key":"S0963548320000553_ref14","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(92)90051-G"},{"key":"S0963548320000553_ref19","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2015.12.003"},{"key":"S0963548320000553_ref6","unstructured":"[6] Enomoto, H. , Kaneko, A. and Tuza, Z. (1988) Graphs of order n and minimum degree n\/4. In Combinatorics (Proc. Coll. Math. Soc. J\u00e1nos Bolyai, Eger, 1987), pp. 213\u2013220. North-Holland."},{"key":"S0963548320000553_ref24","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2012.11.025"},{"key":"S0963548320000553_ref26","first-page":"211","article-title":"A note on the path cover number of regular graphs","volume":"43","author":"Magnant","year":"2009","journal-title":"Australas. J. Combin."},{"key":"S0963548320000553_ref9","unstructured":"[9] H\u00e4ggkvist, R. (1978) Unsolved problems. In Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely 1976), Vol. 18 of Colloquia Mathematica Societatis J\u00e1nos Bolyai. North-Holland."},{"key":"S0963548320000553_ref12","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(80)90042-8"},{"key":"S0963548320000553_ref22","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2013.01.005"},{"key":"S0963548320000553_ref21","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2010.12.006"},{"key":"S0963548320000553_ref7","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190020205"},{"key":"S0963548320000553_ref3","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70496-5"},{"key":"S0963548320000553_ref16","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190180802"},{"key":"S0963548320000553_ref10","doi-asserted-by":"publisher","DOI":"10.37236\/7109"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548320000553","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,6,10]],"date-time":"2021-06-10T14:34:58Z","timestamp":1623335698000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548320000553\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,12,18]]},"references-count":28,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,7]]}},"alternative-id":["S0963548320000553"],"URL":"https:\/\/doi.org\/10.1017\/s0963548320000553","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,12,18]]},"assertion":[{"value":"\u00a9 The Author(s), 2020. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}}]}}