Complete Minors in Graphs Without Sparse Cuts

DOI10.1093/IMRN/RNZ086MaRDI QIDQ5068162zbMATH OpenOpenAlexWikidataFDO

Authors Michael Krivelevich, Rajko Nenadov

Publication date 5 April 2022

Published in IMRN. International Mathematics Research Notices (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Graph minors (05C83) Combinatorics (05-XX) Combinatorial probability (60Cxx)

Recommendations

• Complete minors in \(K_{s,s}\)-free graphs
• Minimal Split Completions of Graphs
• Graphs without minor complete subgraphs
• Complete minors in complements of nonseparating planar graphs
• scientific article; zbMATH DE number 969977
• Minimum cuts and sparsification in hypergraphs
• scientific article; zbMATH DE number 1495914
• Cutsets in perfect and minimal imperfect graphs

Cites work

• scientific article; zbMATH DE number 1003278 (Why is no real title available?)
• scientific article; zbMATH DE number 4027516 (Why is no real title available?)
• scientific article; zbMATH DE number 1156585 (Why is no real title available?)
• scientific article; zbMATH DE number 964896 (Why is no real title available?)
• A Separator Theorem for Nonplanar Graphs
• An extremal function for contractions of graphs
• Approximate counting, uniform generation and rapidly mixing Markov chains
• Asymptotic enumeration by degree sequence of graphs of high degree
• Asymptotic enumeration by degree sequence of graphs with degrees \(o(n^{1/2})\)
• Complete minors in \(K_{s,s}\)-free graphs
• Dense minors in graphs of large girth
• Difference Equations, Isoperimetric Inequality and Transience of Certain Random Walks
• Eigenvalues and expanders
• Every planar map is four colorable
• Expanders -- how to find them, and what to find in them
• Girth in graphs
• Hadwiger's conjecture is true for almost every graph
• Introduction to Random Graphs
• Lower bound of the Hadwiger number of graphs by their average degree
• Minors in expanding graphs
• Minors in graphs of large girth
• Minors in lifts of graphs
• Minors in random regular graphs
• Non-interactive correlation distillation, inhomogeneous Markov chains, and the reverse Bonami-Beckner inequality
• Optimal Construction of Edge-Disjoint Paths in Random Graphs
• Random regular graphs of high degree
• The extremal function for complete minors
• The isoperimetric number of random regular graphs
• The probabilistic method
• The spectral gap of dense random regular graphs
• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators

Cited in

(11)

• Complete minors in complements of nonseparating planar graphs
• Perfect matching in random graphs is as hard as Tseitin
• Independence number in triangle-free graphs avoiding a clique minor
• Narrowing the \textsf{LOCAL-CONGEST} gaps in sparse networks via expander decompositions
• Hypercube minor-universality
• Minors in small-set expanders
• Forbidden subgraphs and complete partitions
• Complete minors in graphs without sparse cuts
• Well-mixing vertices and almost expanders
• Improved sparse covers for graphs excluding a fixed minor
• Minors, connectivity, and diameter in randomly perturbed sparse graphs

This page was built for publication: Complete Minors in Graphs Without Sparse Cuts

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