2013/11/05 by Jean-Florent Raymond, Raymond, Jean-Florent, Ignasi Sau +3
Computer Science · Mathematics · #05C70 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #G.2.1 #G.2.2 #acm:05C70 #cs.DM #math.CO #msc:05C70
paper · pdf · doi:10.48550/arxiv.1311.1108
17 pages, 2 figures
arxiv created 2015/09/15 · arxiv updated 2015/09/16
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 Erd\H os-Pósa property holds for every r≥ 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(k2r3 polylog~kr) and fr(k) = O(k4r2 polylog~kr).