Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4646983 | Discrete Mathematics | 2016 | 9 Pages |
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
Jean-Florent Raymond, Ignasi Sau, Dimitrios M. Thilikos,