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 metadatas

Cited literature [12 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01347430
Contributor : Jean-Florent Raymond <>
Submitted on : Tuesday, June 12, 2018 - 4:44:56 PM
Last modification on : Friday, October 5, 2018 - 9:14:01 PM

File

edep_v3.pdf
Files produced by the author(s)

Identifiers

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-01347430v2⟩

Share

Metrics

Record views

119

Files downloads

80