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

(30)

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

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)