Minors in expanding graphs

DOI10.1007/S00039-009-0713-ZMaRDI QIDQ1028516zbMATHOpenAlexFDO

Authors Michael Krivelevich, Benny Sudakov

Publication date 6 July 2009

Published in Geometric and Functional Analysis. GAFA (Search for Journal in Brave)

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

zbMATH Keywords

extremal problemgraph minors

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Extremal problems in graph theory (05C35) Graph minors (05C83)

Abstract: Extending several previous results we obtained nearly tight estimates on the maximum size of a clique-minor in various classes of expanding graphs. These results can be used to show that graphs without short cycles and other H-free graphs contain large clique-minors, resolving some open questions in this area.

Recommendations

• Small complete minors above the extremal edge density
• Small minors in dense graphs
• On the extremal function for graph minors
• Logarithmically small minors and topological minors
• A lower bound on the average degree forcing a minor

Cited in

(17)

• Waiter-Client and Client-Waiter planarity, colorability and minor games
• Finding and using expanders in locally sparse graphs
• A randomized embedding algorithm for trees
• Finding large expanders in graphs: from topological minors to induced subgraphs
• Minors in graphs of large girth
• Minors in random regular graphs
• Complete Minors in Graphs Without Sparse Cuts
• Small minors in dense graphs
• Breaking the degeneracy barrier for coloring graphs with no \(K_t\) minor
• Clique immersion in graphs without a fixed bipartite graph
• Recent progress towards Hadwiger's conjecture
• Polynomial expansion and sublinear separators
• Small complete minors above the extremal edge density
• Dependent random choice
• Crux, space constraints and subdivisions
• Minors, embeddability, and extremal problems for hypergraphs
• Clique minors in graphs with a forbidden subgraph

This page was built for publication: Minors in expanding graphs

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