An edge variant of the Erdős–Pósa property - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Article Dans Une Revue Discrete Mathematics Année : 2016

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

Résumé

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).
Fichier principal
Vignette du fichier
edep.pdf (434.78 Ko) Télécharger le fichier
Origine : Fichiers éditeurs autorisés sur une archive ouverte
Loading...

Dates et versions

lirmm-01347430 , version 1 (04-10-2017)
lirmm-01347430 , version 2 (12-06-2018)

Identifiants

Citer

Jean-Florent Raymond, Ignasi Sau, Dimitrios M. Thilikos. An edge variant of the Erdős–Pósa property. Discrete Mathematics, 2016, 339 (8), pp.2027-2035. ⟨10.1016/j.disc.2016.03.004⟩. ⟨lirmm-01347430v1⟩
172 Consultations
211 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More