An edge variant of the Erdős-Pósa property - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Communication Dans Un Congrès Année : 2014

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

Résumé

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 et versions

Identifiants

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

Citer

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⟩
126 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More