Cycles of given size in a dense graph

Daniel John Harvey, David Wood

Research output: Contribution to journalArticleResearchpeer-review

4 Citations (Scopus)

Abstract

We generalize a result of Corr´adi and Hajnal and show that every graph with average degree at least 4 3 kr contains k vertex disjoint cycles, each of order at least r, as long as k ≥ 6. This bound is sharp when r = 3.
Original languageEnglish
Pages (from-to)2336-2349
Number of pages14
JournalSIAM Journal on Discrete Mathematics
Volume29
Issue number4
DOIs
Publication statusPublished - 2015

Keywords

  • cycles
  • graph minors
  • average degree

Cite this