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

DOI10.1112/JLMS.12019MaRDI QIDQ5357340zbMATH OpenOpenAlexWikidataFDO

Authors Hong Liu, Richard Montgomery

Publication date 15 September 2017

Published in Journal of the London Mathematical Society (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1605.07791

zbMATH Keywords

Maders conjecture

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38) Graph minors (05C83)

Abstract: Given any integers $s,tgeq2$, we show 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 $c{d}^{frac12fracss-1}$ vertices. In particular, when $s=2$ this resolves in a strong sense the conjecture of Mader in 1999 that every $C_4$-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)$.

Recommendations

• Subdivisions of a large clique in \(C_6\)-free graphs
• Large Topological Cliques in Graphs Without a 4-Cycle
• \(C_4\)-free subgraphs with large average degree
• Every graph of sufficiently large average degree contains a C₄-free subgraph of large average degree
• Induced subdivisions in \(K_{s,s}\)-free graphs of large average degree

Cited in

(24)

• Every graph of sufficiently large average degree contains a C₄-free subgraph of large average degree
• Immersion of complete digraphs in Eulerian digraphs
• Ramsey numbers of cycles versus general graphs
• Induced subdivisions in \(K_{s,s}\)-free graphs of large average degree
• Nested cycles with no geometric crossings
• Extremal density for sparse minors and subdivisions
• Rainbow clique subdivisions
• Balanced Subdivisions of a Large Clique in Graphs with High Average Degree
• Separating path systems of almost linear size
• Nested cycles with no geometric crossings
• Large Topological Cliques in Graphs Without a 4-Cycle
• Disjoint isomorphic balanced clique subdivisions
• \(C_4\)-free subgraphs with large average degree
• How to build a pillar: a proof of Thomassen's conjecture
• Towards the Erdős-Gallai cycle decomposition conjecture
• Many Hamiltonian subsets in large graphs with given density
• Balanced subdivisions of cliques in graphs
• Crux and Long Cycles in Graphs
• Clique immersion in graphs without a fixed bipartite graph
• Crux, space constraints and subdivisions
• Well-mixing vertices and almost expanders
• Towards the Erdős-Gallai cycle decomposition conjecture
• Subdivisions of a large clique in \(C_6\)-free graphs
• A solution to Erdős and Hajnal’s odd cycle problem

This page was built for publication: A proof of Mader's conjecture on large clique subdivisions in \(C_4\)-free graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5357340)