Minors in expanding graphs

DOI10.1007/S00039-009-0713-ZzbMATH Open1227.05230arXiv0707.0133OpenAlexW2129812873MaRDI QIDQ1028516FDOQ1028516

Michael Krivelevich, Benny Sudakov

Publication date: 6 July 2009

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

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.

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)

Cited In (15)

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

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)