Average degree conditions forcing a minor

MaRDI QIDQ259170zbMATHFDO

Authors Daniel J. Harvey, David R. Wood

Publication date 11 March 2016

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

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

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

average degreegraph minors

Mathematics Subject Classification ID

Graph minors (05C83)

Abstract: Mader first proved that high average degree forces a given graph as a minor. Often motivated by Hadwiger's Conjecture, much research has focused on the average degree required to force a complete graph as a minor. Subsequently, various authors have consider the average degree required to force an arbitrary graph $H$ as a minor. Here, we strengthen (under certain conditions) a recent result by Reed and Wood, giving better bounds on the average degree required to force an $H$-minor when $H$ is a sparse graph with many high degree vertices. This solves an open problem of Reed and Wood, and also generalises (to within a constant factor) known results when $H$ is an unbalanced complete bipartite graph.

Recommendations

• A lower bound on the average degree forcing a minor
• Forcing a sparse minor
• Extremal density for sparse minors and subdivisions
• Forcing unbalanced complete bipartite minors
• Complete minors and average degree: A short proof

Cites work

• scientific article; zbMATH DE number 3865318 (Why is no real title available?)
• An extremal function for contractions of graphs
• Connected Domination and Spanning Trees with Many Leaves
• Contractions to k₈
• Dense graphs have \(K_{3,t}\) minors
• Extremal functions for graph minors
• Forcing a sparse minor
• Forcing unbalanced complete bipartite minors
• Graph theory
• Hadwiger's conjecture
• Hadwiger's conjecture is true for almost every graph
• Homomorphieeigenschaften und mittlere Kantendichte von Graphen
• Homomorphiesätze für Graphen
• 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 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

Cited in

(9)

• Forcing large complete (topological) minors in infinite graphs
• Forcing finite minors in sparse infinite graphs by large-degree assumptions
• Asymptotic density of graphs excluding disconnected minors
• The extremal function for disconnected minors
• A lower bound on the average degree forcing a minor
• The extremal function for Petersen minors
• Forcing a sparse minor
• Extremal density for sparse minors and subdivisions
• Forcing a K_r minor by high external connectivity

This page was built for publication: Average degree conditions forcing a minor

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