The Erdős-Pósa property for clique minors in highly connected graphs

DOI10.1016/J.JCTB.2011.08.001MaRDI QIDQ412171zbMATH OpenOpenAlexFDO

Authors Reinhard Diestel, Ken-ichi Kawarabayashi, Paul Wollan

Publication date 4 May 2012

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

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

zbMATH Keywords

clique minorpackingdisjoint cyclesErdős-Pósa

Mathematics Subject Classification ID

Connectivity (05C40) Graph minors (05C83)

Abstract: We prove the existence of a function f: N^2 -> N such that for all p,k in N every (k(p-3) + 14p+14) - connected graph either has k disjoint K_p minors or contains a set of at most f(p,k) vertices whose deletion kills all its K_p minors. For fixed p > 4, the connectivity bound of about k(p-3) is smallest possible, up to an additive constant: if we assume less connectivity in terms of k, there will be no such function f.

Recommendations

• The Erdős-Pósa property for odd cycles in highly connected graphs
• The Erdős-Pósa property for odd cycles in graphs of large connectivity
• A tight Erdős-Pósa function for wheel minors
• A tight Erdős-Pósa function for planar minors
• Highly parity linked graphs

Cites work

• scientific article; zbMATH DE number 3215864 (Why is no real title available?)
• An improved linear edge bound for graph linkages
• Graph minors. V. Excluding a planar graph
• Graph minors. VII: Disjoint paths on a surface
• Graph minors. XVI: Excluding a non-planar graph
• Graph minors. XVII: Taming a vortex
• Graph theory
• Graphs on surfaces
• Linear connectivity forces large complete bipartite minors
• On the excluded minor structure theorem for graphs of large tree-width
• \(K_{6}\) minors in large 6-connected graphs

Cited in

(14)

• Packing and covering immersion-expansions of planar sub-cubic graphs
• The Erdős-Pósa property for edge-disjoint immersions in 4-edge-connected graphs
• The Erdős-Pósa property for odd cycles in graphs of large connectivity
• A tight Erdős-Pósa function for wheel minors
• Excluded Forest Minors and the Erdős–Pósa Property
• Recent techniques and results on the Erdős-Pósa property
• On the excluded minor structure theorem for graphs of large tree-width
• List-coloring graphs without subdivisions and without immersions
• Packing and covering immersion models of planar subcubic graphs
• Random graphs containing few disjoint excluded minors
• Many disjoint dense subgraphs versus large \(k\)-connected subgraphs in large graphs with given edge density
• Erdös-Pósa Property of Obstructions to Interval Graphs
• The Erdős-Pósa property for odd cycles in highly connected graphs
• An \(O(\log \mathrm{OPT})\)-approximation for covering and packing minor models of \(\theta _r\)

This page was built for publication: The Erdős-Pósa property for clique minors in highly connected graphs

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