An edge variant of the Erdős–Pósa property - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Journal Articles Discrete Mathematics Year : 2016

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


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_v3.pdf (329.74 Ko) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

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



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-01347430v2⟩
173 View
218 Download



Gmail Mastodon Facebook X LinkedIn More