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)$
Type de document :
Communication dans un congrès
EuroComb: European Conference on Combinatorics, Graph Theory and Applications, Sep 2013, Pisa, Italy. Springer, 7th European Conference on Combinatorics, Graph Theory and Applications, 16, pp.13-18, 2013, CRM Series. 〈http://www.eurocomb2013.it/index.php?pg=webshow&id=1〉. 〈10.1007/978-88-7642-475-5_3〉
Liste complète des métadonnées

Littérature citée [20 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01083659
Contributeur : Dimitrios M. Thilikos <>
Soumis le : lundi 17 novembre 2014 - 16:32:43
Dernière modification le : vendredi 5 octobre 2018 - 21:14:01

Fichier

pgept.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

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. Springer, 7th European Conference on Combinatorics, Graph Theory and Applications, 16, pp.13-18, 2013, CRM Series. 〈http://www.eurocomb2013.it/index.php?pg=webshow&id=1〉. 〈10.1007/978-88-7642-475-5_3〉. 〈lirmm-01083659〉

Partager

Métriques

Consultations de la notice

180

Téléchargements de fichiers

407