Abstract
Given any integers s,t⩾2, 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(s−1) 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,t ‐free graphs suggests our result is tight up to the constant c(s,t).
Original language | English |
---|---|
Pages (from-to) | 203-222 |
Number of pages | 20 |
Journal | Journal of the London Mathematical Society |
Volume | 95 |
Issue number | 1 |
Early online date | 6 Jan 2017 |
DOIs | |
Publication status | Published - Feb 2017 |
Keywords
- 05C35 (primary)
- 05C38
- 05C83 (secondary)