An edge variant of the Erdős–Pósa property

Abstract : For every r ∈ N, we denote by θ r the multigraph with two vertices and r parallel edges. Given a graph G, we say that a subgraph H of G is a model of θ r in G if H contains θ r as a contraction. We prove that the following edge variant of the Erdős–Pósa property holds for every r 2: if G is a graph and k is a positive integer, then either G contains a packing of k mutually edge-disjoint models of θ r , or it contains a set S of f r (k) edges such that G \ S has no θ r-model, for both f r (k) = O(k 2 r 3 polylog kr) and f r (k) = O(k 4 r 2 polylog kr).
Type de document :
Article dans une revue
Discrete Mathematics, Elsevier, 2016, 339 (8), pp.2027-2035. 〈10.1016/j.disc.2016.03.004〉
Liste complète des métadonnées

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

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01347430
Contributeur : Isabelle Gouat <>
Soumis le : mercredi 4 octobre 2017 - 15:37:54
Dernière modification le : jeudi 11 janvier 2018 - 06:26:13

Fichier

edep.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

Collections

Citation

Jean-Florent Raymond, Ignasi Sau, Dimitrios M. Thilikos. An edge variant of the Erdős–Pósa property. Discrete Mathematics, Elsevier, 2016, 339 (8), pp.2027-2035. 〈10.1016/j.disc.2016.03.004〉. 〈lirmm-01347430〉

Partager

Métriques

Consultations de la notice

106

Téléchargements de fichiers

17