Περίληψη:
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.
Συγγραφείς:
Raymond, J.-F.
Sau, I.
Thilikos, D.M.
