Article ID Journal Published Year Pages File Type
4656719 Journal of Combinatorial Theory, Series B 2016 16 Pages PDF
Abstract

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 Erdős–Pósa 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)f(k) satisfying the following. For any 4-edge-connected graph G=(V,E)G=(V,E), either G has k   edge-disjoint odd cycles or there exists an edge set F⊆EF⊆E with |F|≤f(k)|F|≤f(k) such that G−FG−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 ε>0ε>0, if k=O((log⁡log⁡log⁡n)1/2−ε)k=O((log⁡log⁡log⁡n)1/2−ε), 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].

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,