Polynomial Gap Extensions of the Erdős-Pósa Theorem

Résumé : Given a graph $H$, we denote by ${\cal M}(H)$ all graphs that can be contracted to $H$. The following extension of the Erd\H{o}s-Pósa Theorem holds: for every $h$-vertex planar graph $H$, there exists a function $f_{H}$ such that every graph $G$, either contains $k$ disjoint copies of graphs in ${\cal M}(H)$, or contains a set of $f_{H}(k)$ vertices meeting every subgraph of $G$ that belongs in ${\cal M}(H)$. In this paper we prove that this is the case for every graph $H$ of pathwidth at most 2 and, in particular, that $f_{H}(k) = 2^{O(h^2)}\cdot k^{2}\cdot \log k$. As a main ingredient of the proof of our result, we show that for every graph $H$ on $h$ vertices and pathwidth at most 2, either $G$ contains $k$ disjoint copies of $H$ as a minor or the treewidth of $G$ is upper-bounded by $2^{O(h^2)}\cdot k^{2}\cdot \log k$. We finally prove that the exponential dependence on $h$ in these bounds can be avoided if $H=K_{2,r}$. In particular, we show that $f_{K_{2,r}}=O(r^2\cdot k^2)$
Document type :
Conference papers
Liste complète des métadonnées

Cited literature [20 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01083659
Contributor : Dimitrios M. Thilikos <>
Submitted on : Monday, November 17, 2014 - 4:32:43 PM
Last modification on : Friday, October 5, 2018 - 9:14:01 PM

File

pgept.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Jean-Florent Raymond, Dimitrios M. Thilikos. Polynomial Gap Extensions of the Erdős-Pósa Theorem. EuroComb: European Conference on Combinatorics, Graph Theory and Applications, Sep 2013, Pisa, Italy. pp.13-18, ⟨10.1007/978-88-7642-475-5_3⟩. ⟨lirmm-01083659⟩

Share

Metrics

Record views

193

Files downloads

468