Polynomial Gap Extensions of the Erdős-Pósa Theorem - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2013

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


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)$
Fichier principal
Vignette du fichier
pgept.pdf (380.44 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

lirmm-01083659 , version 1 (17-11-2014)



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⟩
198 View
401 Download



Gmail Facebook X LinkedIn More