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).
Type de document :
Communication dans un congrès
ICGT: International Colloquium on Graph Theory and Combinatorics, Jun 2014, Grenoble, France. 2014
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00904544
Contributeur : Dimitrios M. Thilikos <>
Soumis le : jeudi 14 novembre 2013 - 16:23:46
Dernière modification le : jeudi 11 janvier 2018 - 06:26:13

Lien texte intégral

Identifiants

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

Collections

Citation

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. 2014. 〈lirmm-00904544〉

Partager

Métriques

Consultations de la notice

120