A proof of Mader's conjecture on large clique subdivisions in C4‐free graphs

Research output: Contribution to journalArticlepeer-review

Authors

Colleges, School and Institutes

External organisations

  • Warwick University

Abstract

Given any integers s,t2, we show that there exists some c=c(s,t)>0 such that any Ks,t‐free graph with average degree d contains a subdivision of a clique with at least cds/2(s1) vertices. In particular, when s=2, this resolves in a strong sense the conjecture of Mader in 1999 that every C4‐free graph has a subdivision of a clique with order linear in the average degree of the original graph. In general, the widely conjectured asymptotic behaviour of the extremal density of Ks,‐free graphs suggests our result is tight up to the constant c(s,t).

Details

Original languageEnglish
Pages (from-to)203-222
Number of pages20
JournalJournal of the London Mathematical Society
Volume95
Issue number1
Early online date6 Jan 2017
Publication statusPublished - Feb 2017

Keywords

  • 05C35 (primary), 05C38, 05C83 (secondary)