Forcing a sparse minor

DOI10.1017/S0963548315000073MaRDI QIDQ5366891zbMATH OpenOpenAlexFDO

Authors David R. Wood, Bruce Reed

Publication date 10 October 2017

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph minors (05C83) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Abstract: This paper addresses the following question for a given graph $H$: what is the minimum number $f(H)$ such that every graph with average degree at least $f(H)$ contains $H$ as a minor? Due to connections with Hadwiger's Conjecture, this question has been studied in depth when $H$ is a complete graph. Kostochka and Thomason independently proved that $f(K_t)=ctsqrtlnt$. More generally, Myers and Thomason determined $f(H)$ when $H$ has a super-linear number of edges. We focus on the case when $H$ has a linear number of edges. Our main result, which complements the result of Myers and Thomason, states that if $H$ has $t$ vertices and average degree $d$ at least some absolute constant, then $f(H)leq3.895sqrtlnd,t$. Furthermore, motivated by the case when $H$ has small average degree, we prove that if $H$ has $t$ vertices and $q$ edges, then $f(H)leqt+6.291q$ (where the coefficient of 1 in the $t$ term is best possible).

Recommendations

• A lower bound on the average degree forcing a minor
• Average degree conditions forcing a minor
• Small minors in dense graphs
• Extremal density for sparse minors and subdivisions
• Forcing unbalanced complete bipartite minors

Cites work

• A Note on Vertex-Disjoint Cycles
• An extremal function for contractions of graphs
• An improved linear edge bound for graph linkages
• Contractions to k₈
• Dense graphs have \(K_{3,t}\) minors
• Density theorems for bipartite graphs and related Ramsey-type results
• Disjoint complete minors and bipartite minors
• Disjoint unions of complete minors
• Existenz n-fach zusammenhängender Teilgraphen in Graphen genügend großer Kantendichte
• Forcing unbalanced complete bipartite minors
• Graph theory
• Hadwiger's conjecture is true for almost every graph
• Homomorphieeigenschaften und mittlere Kantendichte von Graphen
• Homomorphiesätze für Graphen
• Homomorphism theorems for graphs
• scientific article; zbMATH DE number 3865318 (Why is no real title available?)
• scientific article; zbMATH DE number 4101249 (Why is no real title available?)
• scientific article; zbMATH DE number 1870233 (Why is no real title available?)
• Lower bound of the Hadwiger number of graphs by their average degree
• On \(K_{s,t}\)-minors in graphs with given average degree
• On \(K_{s,t}\)-minors in graphs with given average degree. II
• On the maximal number of independent circuits in a graph
• On the maximum density of graphs which have no subcontraction to \(K^ r\).
• The edge-density for \(K_{2,t}\) minors
• The extremal function for \(K_{9}\) minors
• The extremal function for complete minors
• The extremal function for noncomplete minors
• The extremal function for unbalanced bipartite minors
• Weighted sums of certain dependent random variables

Cited in

(21)

• The extremal function for unbalanced bipartite minors
• Degree conditions for the existence of vertex-disjoint cycles and paths: a survey
• On the purity of minor-closed classes of graphs
• The extremal function for Petersen minors
• A lower bound on the average degree forcing a minor
• Forcing finite minors in sparse infinite graphs by large-degree assumptions
• Average degree conditions forcing a minor
• Phase transition of degeneracy in minor-closed families
• Hadwiger's conjecture
• Cycles of Given Size in a Dense Graph
• Small minors in dense graphs
• Extremal density for sparse minors and subdivisions
• Minor-Closed Graph Classes with Bounded Layered Pathwidth
• Extremal functions for sparse minors
• Complete directed minors and chromatic number
• On the extremal function for graph minors
• Tight bounds for divisible subdivisions
• Extremal density for sparse minors and subdivisions
• Product structure of graph classes with bounded treewidth
• Finding dense minors using average degree
• Minors in small-set expanders

This page was built for publication: Forcing a sparse minor

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