Minors in expanding graphs
From MaRDI portal
Publication:1028516
DOI10.1007/S00039-009-0713-ZzbMATH Open1227.05230arXiv0707.0133OpenAlexW2129812873MaRDI QIDQ1028516FDOQ1028516
Authors: 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
Recommendations
Random graphs (graph-theoretic aspects) (05C80) Extremal problems in graph theory (05C35) Graph minors (05C83)
Cited In (17)
- Minors, embeddability, and extremal problems for hypergraphs
- 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
- Finding and using expanders in locally sparse graphs
- Small complete minors above the extremal edge density
- Small minors in dense graphs
- Polynomial expansion and sublinear separators
- 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)
