Small Complete Minors Above the Extremal Edge Density
Preprint
Abstract
A fundamental result of Mader from 1972 asserts that a graph of high average degree contains a highly connected subgraph with roughly the same average degree. We prove a lemma showing that one can strengthen Mader's result by replacing the notion of high connectivity by the notion of vertex expansion. Another well known result in graph theory states that for every integer t there is a smallest real c(t) so that every n-vertex graph with c(t)n edges contains a K_t-minor. Fiorini, Joret, Theis and Wood conjectured that if an n-vertex graph G has (c(t)+\epsilon)n edges then G contains a K_t-minor of order at most C(\epsilon)log n. We use our extension of Mader's theorem to prove that such a graph G must contain a K_t-minor of order at most C(\epsilon)log n loglog n. Known constructions of graphs with high girth show that this result is tight up to the loglog n factor.Keywords
All Related Versions
This publication has 12 references indexed in Scilit:
- A Linear-Time Algorithm for Finding a Complete Graph Minor in a Dense GraphSIAM Journal on Discrete Mathematics, 2013
- Small minors in dense graphsEuropean Journal of Combinatorics, 2012
- Minors in Expanding GraphsGeometric and Functional Analysis, 2009
- The Extremal Function for Complete MinorsJournal of Combinatorial Theory, Series B, 2001
- A Sublinear Bipartiteness Tester for Bounded Degree GraphsCombinatorica, 1999
- Highly linked graphsCombinatorica, 1996
- Graph Minors .XIII. The Disjoint Paths ProblemJournal of Combinatorial Theory, Series B, 1995
- Lower bound of the hadwiger number of graphs by their average degreeCombinatorica, 1984
- An extremal function for contractions of graphsMathematical Proceedings of the Cambridge Philosophical Society, 1984
- Homomorphieeigenschaften und mittlere Kantendichte von GraphenMathematische Annalen, 1967