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

Research output: Contribution to journalArticle

Authors

Colleges, School and Institutes

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.

Details

Original languageEnglish
Pages (from-to)170-219
JournalJournal of Combinatorial Theory. Series B
Volume131
Early online date7 Mar 2018
Publication statusPublished - Jul 2018

Keywords

  • Induced subgraphs, Random graphs, Typical structure