Cycles of given size in a dense graph

Daniel John Harvey; David Wood

doi:10.1137/15M100852X

Cycles of given size in a dense graph

Daniel John Harvey, David Wood

School of Mathematics

Research output: Contribution to journal › Article › Research › peer-review

5 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 language	English
Pages (from-to)	2336-2349
Number of pages	14
Journal	SIAM Journal on Discrete Mathematics
Volume	29
Issue number	4
DOIs	https://doi.org/10.1137/15M100852X
Publication status	Published - 2015

Keywords

cycles
graph minors
average degree

Access to Document

10.1137/15M100852X

Cite this

@article{d3058dc8ccb94273ab6c41894360c766,

title = "Cycles of given size in a dense graph",

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.",

keywords = "cycles, graph minors, average degree",

author = "Harvey, {Daniel John} and David Wood",

year = "2015",

doi = "10.1137/15M100852X",

language = "English",

volume = "29",

pages = "2336--2349",

journal = "SIAM Journal on Discrete Mathematics",

issn = "0895-4801",

publisher = "Society for Industrial & Applied Mathematics (SIAM)",

number = "4",

}

TY - JOUR

T1 - Cycles of given size in a dense graph

AU - Harvey, Daniel John

AU - Wood, David

PY - 2015

Y1 - 2015

N2 - 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.

AB - 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.

KW - cycles

KW - graph minors

KW - average degree

UR - http://epubs.siam.org/doi/pdf/10.1137/15M100852X

U2 - 10.1137/15M100852X

DO - 10.1137/15M100852X

M3 - Article

SN - 0895-4801

VL - 29

SP - 2336

EP - 2349

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

IS - 4

ER -

Cycles of given size in a dense graph

Abstract

Keywords

Access to Document

Other files and links

Hadwiger's graph colouring conjecture

Cite this

Cycles of given size in a dense graph

Abstract

Keywords

Access to Document

Other files and links

Projects

Hadwiger's graph colouring conjecture

Cite this