Article ID Journal Published Year Pages File Type
4646983 Discrete Mathematics 2016 9 Pages PDF
Abstract

For every  r∈Nr∈N, we denote by θrθr the multigraph with two vertices and rr parallel edges. Given a graph GG, we say that a subgraph HH of GG is a model of  θrθrin  GG if HH contains θrθr as a contraction. We prove that the following edge variant of the Erdős–Pósa property holds for every r⩾2r⩾2: if GG is a graph and kk is a positive integer, then either GG contains a packing of kk mutually edge-disjoint models of θrθr, or it contains a set SS of fr(k)fr(k) edges such that G∖SG∖S has no θrθr-model, for both fr(k)=O(k2r3polylogkr)fr(k)=O(k2r3polylogkr) and fr(k)=O(k4r2polylogkr)fr(k)=O(k4r2polylogkr).

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , ,