Balanced Subdivisions of a Large Clique in Graphs with High Average Degree

DOI10.1137/22M1511266MaRDI QIDQ6161261zbMATH OpenFDO

Authors Yan Wang

Publication date 27 June 2023

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

adjusterclique subdivisionexpander

Mathematics Subject Classification ID

Vertex degrees (05C07) Extremal problems in graph theory (05C35) Paths and cycles (05C38) Expander graphs (05C48) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: In 1984, Thomassen conjectured that for every constant $kinmathbbN$, there exists $d$ such that every graph with average degree at least $d$ contains a balanced subdivision of a complete graph on $k$ vertices, i.e. a subdivision in which each edge is subdivided the same number of times. Recently, Liu and Montgomery confirmed Thomassen's conjecture. We show that for every constant $0<c<1/2$, every graph with average degree at least $d$ contains a balanced subdivision of a complete graph of size at least $Omega(d^c)$. Note that this bound is almost optimal. Moreover, we show that every sparse expander with minimum degree at least $d$ contains a balanced subdivision of a complete graph of size at least $Omega(d)$.

Recommendations

• Disjoint isomorphic balanced clique subdivisions
• Subdivisions of $K_{r+2}$ in Graphs of Average Degree at Least $r+\varepsilon$ and Large but Constant Girth
• A note on Thomassen's conjecture
• A proof of Mader's conjecture on large clique subdivisions in \(C_4\)-free graphs
• Subdivisions of a graph of maximal degree n+1 in graphs of average degree n+ and large girth

Cites work

• A proof of Mader's conjecture on large clique subdivisions in \(C_4\)-free graphs
• A solution to Erdős and Hajnal’s odd cycle problem
• An extremal problem for subdivisions ofK?5
• Disjoint isomorphic balanced clique subdivisions
• Eine Verallgemeinerung des n-fachen Zusammenhangs für Graphen
• Expander graphs and their applications
• Expander graphs in pure and applied mathematics
• Hinreichende Bedingungen für die Existenz von Teilgraphen, die zu einem vollständigen Graphen homöomorph sind
• Homomorphieeigenschaften und mittlere Kantendichte von Graphen
• scientific article; zbMATH DE number 4164908 (Why is no real title available?)
• Improved Bounds for Topological Cliques in Graphs of Large Girth
• Large Topological Cliques in Graphs Without a 4-Cycle
• Proof of a conjecture of Mader, Erdős and Hajnal on topological complete subgraphs
• Subdivisions of a large clique in \(C_6\)-free graphs
• Subdivisions of graphs with large minimum degree
• Topological Cliques in Graphs
• Topological cliques in graphs II
• Topological minors in graphs of large girth

Cited in

(5)

• Topological Cliques in Graphs
• Disjoint isomorphic balanced clique subdivisions
• Balanced subdivisions of cliques in graphs
• Rainbow clique subdivisions
• Extremal density for subdivisions with length or sparsity constraints

This page was built for publication: Balanced Subdivisions of a Large Clique in Graphs with High Average Degree

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