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

Richard Montgomery; Hong Liu

doi:10.1112/jlms.12019

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

Richard Montgomery, Hong Liu

Mathematics

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

124 Downloads (Pure)

Abstract

Given any integers s,t⩾2, we show that there exists some c=c(s,t)>0 such that any K_s,t‐free graph with average degree d contains a subdivision of a clique with at least cds^/2⁽s⁻¹⁾ vertices. In particular, when s=2, this resolves in a strong sense the conjecture of Mader in 1999 that every C₄‐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 K_s,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	https://doi.org/10.1112/jlms.12019
Publication status	Published - Feb 2017

Keywords

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

Access to Document

10.1112/jlms.12019Licence: None: All rights reserved

Hong_Liu_and_Richard_Montgomery_A_proof_of_Mader's_conjecture_on_large_clique_Journal_of_the_London_Mathematical_Society_2018
This is the accepted version of the following article: Liu, H. and Montgomery, R. (2017), A proof of Mader's conjecture on large clique subdivisions in C 4 ‐free graphs. J. London Math. Soc., 95: 203-222 which has been published in final form at doi:10.1112/jlms.12019.
Accepted author manuscript, 429 KBLicence: Other (please specify with Rights Statement)

https://londmathsoc.onlinelibrary.wiley.com/doi/full/10.1112/jlms.12019Licence: None: All rights reserved

Cite this

@article{d8be4098b0d7449fa5a81b0a1fd10fde,

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

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

keywords = "05C35 (primary), 05C38, 05C83 (secondary)",

author = "Richard Montgomery and Hong Liu",

year = "2017",

month = feb,

doi = "10.1112/jlms.12019",

language = "English",

volume = "95",

pages = "203--222",

journal = "Journal of the London Mathematical Society",

issn = "0024-6107",

publisher = "London Mathematical Society",

number = "1",

}

TY - JOUR

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

AU - Montgomery, Richard

AU - Liu, Hong

PY - 2017/2

Y1 - 2017/2

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

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

KW - 05C35 (primary)

KW - 05C38

KW - 05C83 (secondary)

U2 - 10.1112/jlms.12019

DO - 10.1112/jlms.12019

M3 - Article

SN - 0024-6107

VL - 95

SP - 203

EP - 222

JO - Journal of the London Mathematical Society

JF - Journal of the London Mathematical Society

IS - 1

ER -