Excluded Forest Minors and the Erdős–Pósa Property

DOI10.1017/S0963548313000266zbMath1282.05200arXiv1204.5192MaRDI QIDQ5397727

Samuel Fiorini, David R. Wood, Gwenaël Joret

Publication date: 24 February 2014

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

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

zbMATH Keywords

\(\mathcal F\)-transversal

Mathematics Subject Classification ID

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

Related Items (7)

An edge variant of the Erdős-Pósa property ⋮ A Tighter Erdős-Pósa Function for Long Cycles ⋮ Recent techniques and results on the Erdős-Pósa property ⋮ A Tight Erdös--Pósa Function for Wheel Minors ⋮ Erdös--Pósa from Ball Packing ⋮ An \(O(\log \mathrm{OPT})\)-approximation for covering and packing minor models of \(\theta _r\) ⋮ $K_4$-Subdivisions Have the Edge-Erdös--Pósa Property

Cites Work

• Unnamed Item
• The Erdős-Pósa property for clique minors in highly connected graphs
• Graph theoretic concepts in computer science. 36th international workshop, WG 2010, Zarós, Crete, Greece, June 28--30, 2010. Revised papers
• Parameterized and exact computation. 5th international symposium, IPEC 2010, Chennai, India, December 13--15, 2010. Proceedings
• Algorithms -- ESA 2011. 19th annual European symposium, Saarbrücken, Germany, September 5--9, 2011. Proceedings
• Graph minors. XX: Wagner's conjecture
• The structure of the models of decidable monadic theories of graphs
• Integer programming and combinatorial optimization. 14th international conference, IPCO 2010, Lausanne, Switzerland, June 9--11, 2010. Proceedings
• Graph minors. V. Excluding a planar graph
• Ramanujan graphs
• Quickly excluding a forest
• Upper bounds on the size of obstructions and intertwines
• The vertex separation and search number of a graph
• Quickly excluding a planar graph
• On tree width, bramble size, and expansion
• Strengthening Erdös-Pósa property for minor-closed graph classes
• Graph Minors I: A Short Proof of the Path-width Theorem
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• On Independent Circuits Contained in a Graph

This page was built for publication: Excluded Forest Minors and the Erdős–Pósa Property