{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,18]],"date-time":"2026-01-18T04:42:43Z","timestamp":1768711363129,"version":"3.49.0"},"reference-count":13,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2018,3,9]],"date-time":"2018-03-09T00:00:00Z","timestamp":1520553600000},"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":[[2018,5]]},"abstract":"<jats:p>Let <jats:italic>k<\/jats:italic> \u2a7e 3 be an integer, <jats:italic>h<jats:sub>k<\/jats:sub><\/jats:italic>(<jats:italic>G<\/jats:italic>) be the number of vertices of degree at least 2<jats:italic>k<\/jats:italic> in a graph <jats:italic>G<\/jats:italic>, and \u2113<jats:sub><jats:italic>k<\/jats:italic><\/jats:sub>(<jats:italic>G<\/jats:italic>) be the number of vertices of degree at most 2<jats:italic>k<\/jats:italic> \u2212 2 in <jats:italic>G<\/jats:italic>. Dirac and Erd\u0151s proved in 1963 that if <jats:italic>h<jats:sub>k<\/jats:sub><\/jats:italic>(<jats:italic>G<\/jats:italic>) \u2212 \u2113<jats:sub><jats:italic>k<\/jats:italic><\/jats:sub>(<jats:italic>G<\/jats:italic>) \u2a7e <jats:italic>k<\/jats:italic><jats:sup>2<\/jats:sup> + 2<jats:italic>k<\/jats:italic> \u2212 4, then <jats:italic>G<\/jats:italic> contains <jats:italic>k<\/jats:italic> vertex-disjoint cycles. For each <jats:italic>k<\/jats:italic> \u2a7e 2, they also showed an infinite sequence of graphs <jats:italic>G<jats:sub>k<\/jats:sub><\/jats:italic>(<jats:italic>n<\/jats:italic>) with <jats:italic>h<jats:sub>k<\/jats:sub><\/jats:italic>(<jats:italic>G<jats:sub>k<\/jats:sub><\/jats:italic>(<jats:italic>n<\/jats:italic>)) \u2212 \u2113<jats:sub><jats:italic>k<\/jats:italic><\/jats:sub>(<jats:italic>G<jats:sub>k<\/jats:sub><\/jats:italic>(<jats:italic>n<\/jats:italic>)) = 2<jats:italic>k<\/jats:italic> \u2212 1 such that <jats:italic>G<jats:sub>k<\/jats:sub><\/jats:italic>(<jats:italic>n<\/jats:italic>) does not have <jats:italic>k<\/jats:italic> disjoint cycles. Recently, the authors proved that, for <jats:italic>k<\/jats:italic> \u2a7e 2, a bound of 3<jats:italic>k<\/jats:italic> is sufficient to guarantee the existence of <jats:italic>k<\/jats:italic> disjoint cycles, and presented for every <jats:italic>k<\/jats:italic> a graph <jats:italic>G<\/jats:italic><jats:sub>0<\/jats:sub>(<jats:italic>k<\/jats:italic>) with <jats:italic>h<jats:sub>k<\/jats:sub><\/jats:italic>(<jats:italic>G<\/jats:italic><jats:sub>0<\/jats:sub>(<jats:italic>k<\/jats:italic>)) \u2212 \u2113<jats:sub><jats:italic>k<\/jats:italic><\/jats:sub>(<jats:italic>G<\/jats:italic><jats:sub>0<\/jats:sub>(<jats:italic>k<\/jats:italic>)) = 3<jats:italic>k<\/jats:italic> \u2212 1 and no <jats:italic>k<\/jats:italic> disjoint cycles. The goal of this paper is to refine and sharpen this result. We show that the Dirac\u2013Erd\u0151s construction is optimal in the sense that for every <jats:italic>k<\/jats:italic> \u2a7e 2, there are only finitely many graphs <jats:italic>G<\/jats:italic> with <jats:italic>h<jats:sub>k<\/jats:sub><\/jats:italic>(<jats:italic>G<\/jats:italic>) \u2212 \u2113<jats:sub><jats:italic>k<\/jats:italic><\/jats:sub>(<jats:italic>G<\/jats:italic>) \u2a7e 2<jats:italic>k<\/jats:italic> but no <jats:italic>k<\/jats:italic> disjoint cycles. In particular, every graph <jats:italic>G<\/jats:italic> with |<jats:italic>V<\/jats:italic>(<jats:italic>G<\/jats:italic>)| \u2a7e 19<jats:italic>k<\/jats:italic> and <jats:italic>h<jats:sub>k<\/jats:sub><\/jats:italic>(<jats:italic>G<\/jats:italic>) \u2212 \u2113<jats:sub><jats:italic>k<\/jats:italic><\/jats:sub>(<jats:italic>G<\/jats:italic>) \u2a7e 2<jats:italic>k<\/jats:italic> contains <jats:italic>k<\/jats:italic> disjoint cycles.<\/jats:p>","DOI":"10.1017\/s0963548318000020","type":"journal-article","created":{"date-parts":[[2018,3,9]],"date-time":"2018-03-09T16:18:19Z","timestamp":1520612299000},"page":"387-397","source":"Crossref","is-referenced-by-count":1,"title":["A Sharp Dirac\u2013Erd\u0151s Type Bound for Large Graphs"],"prefix":"10.1017","volume":"27","author":[{"given":"H. A.","family":"KIERSTEAD","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"A. V.","family":"KOSTOCHKA","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"A.","family":"McCONVEY","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2018,3,9]]},"reference":[{"key":"S0963548318000020_ref13","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(99)00009-6"},{"key":"S0963548318000020_ref12","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2016.05.007"},{"key":"S0963548318000020_ref8","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2007.07.003"},{"key":"S0963548318000020_ref7","unstructured":"Hajnal A. and Szemer\u00e9di E. (1970) Proof of a conjecture of P. Erd\u0151s. In Combinatorial Theory and its Applications II (Proc. Colloq., Balatonf\u00fcred, 1969), North-Holland, pp. 601\u2013623."},{"key":"S0963548318000020_ref6","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70454-0"},{"key":"S0963548318000020_ref4","doi-asserted-by":"publisher","DOI":"10.1007\/BF01901931"},{"key":"S0963548318000020_ref1","doi-asserted-by":"publisher","DOI":"10.1016\/j.aam.2013.12.001"},{"key":"S0963548318000020_ref2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01895727"},{"key":"S0963548318000020_ref3","doi-asserted-by":"publisher","DOI":"10.4153\/CMB-1963-019-5"},{"key":"S0963548318000020_ref11","doi-asserted-by":"publisher","DOI":"10.1007\/s12188-016-0168-8"},{"key":"S0963548318000020_ref5","doi-asserted-by":"publisher","DOI":"10.1007\/s004930050034"},{"key":"S0963548318000020_ref9","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-014-3059-6"},{"key":"S0963548318000020_ref10","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22106"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548318000020","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,14]],"date-time":"2019-04-14T20:56:13Z","timestamp":1555275373000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548318000020\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,3,9]]},"references-count":13,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,5]]}},"alternative-id":["S0963548318000020"],"URL":"https:\/\/doi.org\/10.1017\/s0963548318000020","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,3,9]]}}}