Forbidding induced even cycles in a graph: typical structure and counting

Jaehoon Kim; Daniela Kuhn; Deryk Osthus; Timothy Townsend

doi:10.1016/j.jctb.2018.02.002

Forbidding induced even cycles in a graph: typical structure and counting

Jaehoon Kim, Daniela Kuhn, Deryk Osthus, Timothy Townsend

Mathematics

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

1 Citation (Scopus)

114 Downloads (Pure)

Abstract

We determine, for all $k\geq 6$, the typical structure of graphs that do not contain an induced $2k$-cycle. This verifies a conjecture of Balogh and Butterfield. Surprisingly, the typical structure of such graphs is richer than that encountered in related results. The approach we take also yields an approximate result on the typical structure of graphs without an induced $8$-cycle or without an induced $10$-cycle.

Original language	English
Pages (from-to)	170-219
Journal	Journal of Combinatorial Theory. Series B
Volume	131
Early online date	7 Mar 2018
DOIs	https://doi.org/10.1016/j.jctb.2018.02.002
Publication status	Published - Jul 2018

Keywords

Induced subgraphs
Random graphs
Typical structure

Access to Document

10.1016/j.jctb.2018.02.002

forbiddenInducedlongC2k15Feb18
Checked for eligibility: 20/02/2018
Accepted author manuscript, 499 KBLicence: Creative Commons: Attribution-NonCommercial-NoDerivs (CC BY-NC-ND)

Cite this

@article{ec29aa7222694910b121836221e95342,

title = "Forbidding induced even cycles in a graph: typical structure and counting",

abstract = "We determine, for all $k\geq 6$, the typical structure of graphs that do not contain an induced $2k$-cycle. This verifies a conjecture of Balogh and Butterfield. Surprisingly, the typical structure of such graphs is richer than that encountered in related results. The approach we take also yields an approximate result on the typical structure of graphs without an induced $8$-cycle or without an induced $10$-cycle.",

keywords = "Induced subgraphs, Random graphs, Typical structure",

author = "Jaehoon Kim and Daniela Kuhn and Deryk Osthus and Timothy Townsend",

year = "2018",

month = jul,

doi = "10.1016/j.jctb.2018.02.002",

language = "English",

volume = "131",

pages = "170--219",

journal = "Journal of Combinatorial Theory. Series B",

issn = "0095-8956",

publisher = "Elsevier",

}

TY - JOUR

T1 - Forbidding induced even cycles in a graph: typical structure and counting

AU - Kim, Jaehoon

AU - Kuhn, Daniela

AU - Osthus, Deryk

AU - Townsend, Timothy

PY - 2018/7

Y1 - 2018/7

N2 - We determine, for all $k\geq 6$, the typical structure of graphs that do not contain an induced $2k$-cycle. This verifies a conjecture of Balogh and Butterfield. Surprisingly, the typical structure of such graphs is richer than that encountered in related results. The approach we take also yields an approximate result on the typical structure of graphs without an induced $8$-cycle or without an induced $10$-cycle.

AB - We determine, for all $k\geq 6$, the typical structure of graphs that do not contain an induced $2k$-cycle. This verifies a conjecture of Balogh and Butterfield. Surprisingly, the typical structure of such graphs is richer than that encountered in related results. The approach we take also yields an approximate result on the typical structure of graphs without an induced $8$-cycle or without an induced $10$-cycle.

KW - Induced subgraphs

KW - Random graphs

KW - Typical structure

U2 - 10.1016/j.jctb.2018.02.002

DO - 10.1016/j.jctb.2018.02.002

M3 - Article

SN - 0095-8956

VL - 131

SP - 170

EP - 219

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

ER -

Forbidding induced even cycles in a graph: typical structure and counting

Abstract

Keywords

Access to Document

Fingerprint

Cite this