TY - JOUR
TI - An edge variant of the Erdos-Pósa property
AU - Raymond, J.-F.
AU - Sau, I.
AU - Thilikos, D.M.
JO - DISCRETE MATHEMATICS,
PY - 2016
VL - 339
TODO - 8
SP - 2027-2035
PB - Elsevier B.V.
SN - 0012-365X
TODO - 10.1016/j.disc.2016.03.004
TODO - null
TODO - 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). © 2016 Elsevier B.V. All rights reserved.
ER -