Average degree conditions forcing a minor

zbMATH Open1333.05278arXiv1506.01775MaRDI QIDQ259170FDOQ259170

Authors: Daniel J. Harvey, David R. Wood 

Publication date: 11 March 2016

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

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.

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

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

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

zbMATH Keywords

average degreegraph minors

Mathematics Subject Classification ID

Graph minors (05C83)

Cites Work

• Graph theory
• On the maximum density of graphs which have no subcontraction to \(K^ r\).
• Hadwiger's conjecture is true for almost every graph
• The extremal function for unbalanced bipartite minors
• On \(K_{s,t}\)-minors in graphs with given average degree. II
• The extremal function for complete minors
• The extremal function for noncomplete minors
• The extremal function for \(K_{9}\) minors
• Homomorphiesätze für Graphen
• Homomorphieeigenschaften und mittlere Kantendichte von Graphen
• Hadwiger’s Conjecture
• Title not available (Why is that?)
• An extremal function for contractions of graphs
• Contractions to k₈
• Connected Domination and Spanning Trees with Many Leaves
• Forcing a sparse minor
• Extremal functions for graph minors
• The edge-density for \(K_{2,t}\) minors
• Forcing unbalanced complete bipartite minors
• Dense graphs have \(K_{3,t}\) minors
• Lower bound of the Hadwiger number of graphs by their average degree
• On \(K_{s,t}\)-minors in graphs with given average degree

Cited In (5)

• The extremal function for disconnected minors
• The extremal function for Petersen minors
• Forcing a K_r minor by high external connectivity
• A lower bound on the average degree forcing a minor
• Asymptotic density of graphs excluding disconnected minors

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)