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

Jean-Florent Raymond 1 Ignasi Sau 1 Dimitrios M. Thilikos 2, 1
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
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{\H o}s-P{\'o}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 fr(k) edges meeting all models of θr in G, for both fr(k)=O(k2r3polylog kr) and fr(k)=O(k4r2polylog kr).
Complete list of metadatas
Contributor : Dimitrios M. Thilikos <>
Submitted on : Thursday, November 14, 2013 - 4:23:46 PM
Last modification on : Thursday, November 15, 2018 - 7:52:49 PM

Links full text


  • HAL Id : lirmm-00904544, version 1
  • ARXIV : 1311.1108



Jean-Florent Raymond, Ignasi Sau, Dimitrios M. Thilikos. An edge variant of the Erdős-Pósa property. ICGT: International Colloquium on Graph Theory and combinatorics, Jun 2014, Grenoble, France. ⟨lirmm-00904544⟩



Record views