The Erdős-Pósa property for clique minors in highly connected graphs
From MaRDI portal
Publication:412171
DOI10.1016/J.JCTB.2011.08.001zbMATH Open1239.05172arXiv1003.3915OpenAlexW1988226118MaRDI QIDQ412171FDOQ412171
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)
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.
Full work available at URL: https://arxiv.org/abs/1003.3915
Recommendations
Cites Work
- Graph theory
- Graphs on surfaces
- Title not available (Why is that?)
- Graph minors. V. Excluding a planar graph
- An improved linear edge bound for graph linkages
- \(K_{6}\) minors in large 6-connected graphs
- Graph minors. XVI: Excluding a non-planar graph
- Linear connectivity forces large complete bipartite minors
- Graph minors. VII: Disjoint paths on a surface
- Graph minors. XVII: Taming a vortex
- On the excluded minor structure theorem for graphs of large tree-width
Cited In (14)
- Random graphs containing few disjoint excluded minors
- Excluded Forest Minors and the Erdős–Pósa Property
- An \(O(\log \mathrm{OPT})\)-approximation for covering and packing minor models of \(\theta _r\)
- Packing and covering immersion models of planar subcubic graphs
- Erdös-Pósa Property of Obstructions to Interval Graphs
- On the excluded minor structure theorem for graphs of large tree-width
- Many disjoint dense subgraphs versus large \(k\)-connected subgraphs in large graphs with given edge density
- Packing and covering immersion-expansions of planar sub-cubic 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
- 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 highly connected graphs
- Recent techniques and results on the Erdős-Pósa property
- List-coloring graphs without subdivisions and without immersions
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)
