The extremal function for disconnected minors

DOI10.1016/J.JCTB.2017.04.005MaRDI QIDQ2399354zbMATH OpenOpenAlexFDO

Authors Endre Csóka, Irene Lo, Serguei Norine, Hehui Wu, L. Yepremyan

Publication date 22 August 2017

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1509.01185, http://real.mtak.hu/44110/1/1509.01185v1.pdf

zbMATH Keywords

extremal functionaverage degreecyclesgraph minors

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph minors (05C83)

Abstract: For a graph $H$ let $c(H)$ denote the supremum of $|E(G)|/|V(G)|$ taken over all non-null graphs $G$ not containing $H$ as a minor. We show that ${\displaystyle }$c(H) leq frac{|V(H)|+mathrm{comp}(H)}{2}-1,${\displaystyle }$ when $H$ is a union of cycles, verifying conjectures of Reed and Wood, and Harvey and Wood. We derive the above result from a theorem which allows us to find two vertex disjoint subgraphs with prescribed densities in a sufficiently dense graph, which might be of independent interest.

Recommendations

• Asymptotic density of graphs excluding disconnected minors
• Extremal functions for sparse minors
• The extremal function for noncomplete minors
• On the extremal function for graph minors
• Disjoint unions of complete minors

Cites work

• 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 944226 (Why is no real title available?)
• scientific article; zbMATH DE number 1870233 (Why is no real title available?)
• An extremal function for contractions of graphs
• Average degree conditions forcing a minor
• Contractions to k₈
• Cycles of Given Size in a Dense Graph
• Dense graphs have \(K_{3,t}\) minors
• Disjoint unions of complete minors
• Forcing unbalanced complete bipartite minors
• Homomorphiesätze für Graphen
• Homomorphism theorems for graphs
• Lower bound of the Hadwiger number of graphs by their average degree
• On \(K_{s,t}\)-minors in graphs with given average degree
• On maximal paths and circuits of graphs
• 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

Cited in

(12)

• Extremal functions for sparse minors
• The extremal function for Petersen minors
• Partitioning graphs with linear minimum degree
• Degree conditions for the existence of vertex-disjoint cycles and paths: a survey
• Graph partitions under average degree constraint
• Recent progress towards Hadwiger's conjecture
• A tight Erdős-Pósa function for wheel minors
• Erdős-Pósa from ball packing
• A lower bound on the average degree forcing a minor
• Cycles of Given Size in a Dense Graph
• Asymptotic density of graphs excluding disconnected minors
• On the purity of minor-closed classes of graphs

This page was built for publication: The extremal function for disconnected minors

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