Edge-disjoint odd cycles in 4-edge-connected graphs

Finding edge-disjoint odd cycles is one of the most important problems in graph theory, graph algorithms and combinatorial optimization. One of the difficulties of this problem is that the Erdos Posa property does not hold for odd cycles in general. Motivated by this fact, we prove that for any positive integer k, there exists an integer f (k) satisfying the following. For any 4-edge-connected graph G = (V, E), either G has k edge-disjoint odd cycles or there exists an edge set F subset of E with vertical bar F vertical bar <= f (k) such that G - F is bipartite. We note that the 4-edge-connectivity is best possible in this statement. A similar approach can be applied to an algorithmic question. Suppose that the input graph G is a 4-edge-connected graph with n vertices. We show that, for any epsilon > 0, if k = O((log log log n)(1/2-epsilon)), then the k edge-disjoint odd cycle packing problem in G can be solved in polynomial time in n. This result implies the authors' algorithm for the k edge disjoint paths problem in 4-edge-connected graphs [13]. (C) 2015 Elsevier Inc. All rights reserved.