Skip to Main content Skip to Navigation
Journal articles

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).
Document type :
Journal articles
Complete list of metadata

Cited literature [15 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01347430
Contributor : Isabelle Gouat <>
Submitted on : Wednesday, October 4, 2017 - 3:37:54 PM
Last modification on : Thursday, November 26, 2020 - 3:50:03 PM

File

edep.pdf
Publisher files allowed on an open archive

Identifiers

Citation

Jean-Florent Raymond, Ignasi Sau Valls, 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-01347430v1⟩

Share

Metrics

Record views

126

Files downloads

20