An edge variant of the Erdos-Pósa property

Jean Florent Raymond, Ignasi Sau, Dimitrios M. Thilikos

Research output: Contribution to journalArticlepeer-review


For every r ϵ ℕ, 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 Erdos-Pósa property holds for every ≥ 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 such that G\S has no θr-model, for both fr(k) = O(k2r3polylog kr) and fr(k)=O(k4r2polylog kr).

Original languageEnglish (US)
Pages (from-to)2027-2035
Number of pages9
JournalDiscrete Mathematics
Issue number8
StatePublished - Aug 6 2016


  • Coverings in graphs
  • Erdos-Pósa property
  • Packings in graphs

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'An edge variant of the Erdos-Pósa property'. Together they form a unique fingerprint.

Cite this