Small minors in dense graphs

DOI10.1016/J.EJC.2012.02.003MaRDI QIDQ427808zbMATH OpenOpenAlexFDO

Authors Samuel Fiorini, Gwenaël Joret, Dirk Oliver Theis, David R. Wood

Publication date 18 June 2012

Published in European Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

structural graph theory, logarithmic dependence

Mathematics Subject Classification ID

Density (toughness, etc.) (05C42) Graph minors (05C83)

Abstract: A fundamental result in structural graph theory states that every graph with large average degree contains a large complete graph as a minor. We prove this result with the extra property that the minor is small with respect to the order of the whole graph. More precisely, we describe functions $f$ and $h$ such that every graph with $n$ vertices and average degree at least $f(t)$ contains a $K_t$-model with at most $h(t)cdotlogn$ vertices. The logarithmic dependence on $n$ is best possible (for fixed $t$). In general, we prove that $f(t)leq{2}^{t-1}+eps$. For $tleq4$, we determine the least value of $f(t)$; in particular $f(3)=2+eps$ and $f(4)=4+eps$. For $tleq4$, we establish similar results for graphs embedded on surfaces, where the size of the $K_t$-model is bounded (for fixed $t$).

Recommendations

• Logarithmically small minors and topological minors
• A lower bound on the average degree forcing a minor
• Complete minors and average degree: A short proof
• Minors in expanding graphs
• Forcing a sparse minor

Cites work

• scientific article; zbMATH DE number 3865318 (Why is no real title available?)
• scientific article; zbMATH DE number 52938 (Why is no real title available?)
• A High Girth Graph Construction
• An extremal function for contractions of graphs
• Compact topological minors in graphs
• Extremal functions for graph minors
• Forcing unbalanced complete bipartite minors
• Girth in graphs
• Graphs on surfaces
• Hitting diamonds and growing cacti
• Homomorphieeigenschaften und mittlere Kantendichte von Graphen
• Homomorphiesätze für Graphen
• Improved Bounds for Topological Cliques in Graphs of Large Girth
• Light subgraphs of order at most 3 in large maps of minimum degree 5 on compact 2-manifolds
• Lower bound of the Hadwiger number of graphs by their average degree
• Minors in expanding graphs
• Minors in graphs of large girth
• On \(K_{s,t}\)-minors in graphs with given average degree
• On light subgraphs in plane graphs of minimum degree five
• On the total coloring of planar graphs.
• Small topological complete subgraphs of ``dense graphs
• The extremal function for complete minors
• The extremal function for noncomplete minors
• The extremal function for unbalanced bipartite minors
• Topological subgraphs in graphs of large girth

Cited in

(20)

• Minimum degree and graph minors
• Logarithmically small minors and topological minors
• Dense graphs have \(K_{3,t}\) minors
• Minors in expanding graphs
• Tree densities in sparse graph classes
• A tight Erdős-Pósa function for wheel minors
• Graph minors and minimum degree
• Rainbow Turán number of clique subdivisions
• Automorphisms of the \(k\)-curve graph
• Dense minors in graphs of large girth
• Finding dense minors using average degree
• A lower bound on the average degree forcing a minor
• Small complete minors above the extremal edge density
• Uniform hyperbolicity of the graphs of curves
• Short proofs of some extremal results. II.
• Densities of minor-closed graph families
• scientific article; zbMATH DE number 1870233 (Why is no real title available?)
• Forcing a sparse minor
• Extremal density for sparse minors and subdivisions
• Complete minors and average degree: A short proof

This page was built for publication: Small minors in dense graphs

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