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

DOI10.1112/JLMS.12019zbMATH Open1370.05103arXiv1605.07791OpenAlexW3125259119WikidataQ123219507 ScholiaQ123219507MaRDI QIDQ5357340FDOQ5357340

Authors: Hong Liu, Richard Montgomery 

Publication date: 15 September 2017

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

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

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

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_4\)-free subgraph of large average degree
• Induced subdivisions in \(K_{s,s}\)-free graphs of large average degree

zbMATH Keywords

Maders conjecture

Mathematics Subject Classification ID

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

Cited In (24)

• Immersion of complete digraphs in Eulerian digraphs
• Ramsey numbers of cycles versus general graphs
• Every graph of sufficiently large average degree contains a \(C_4\)-free subgraph 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
• Induced subdivisions in \(K_{s,s}\)-free graphs of large 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
• Towards the Erdős-Gallai cycle decomposition conjecture
• Well-mixing vertices and almost expanders
• 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)