An edge variant of the Erdős-Pósa property - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Conference Papers Year : 2014

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{\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).

Dates and versions

Identifiers

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

Cite

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⟩
128 View
0 Download

Altmetric

Share

More