\input zb-basic \input zb-ioport \iteman{io-port 06070903} \itemau{Kawarabayashi, Ken-Ichi; Kobayashi, Yusuke} \itemti{Edge-disjoint odd cycles in 4-edge-connected graphs.} \itemso{D\"urr, Christoph (ed.) et al., STACS 2012. 29th international symposium on theoretical aspects of computer science, Paris, France, February 29th -- March 3rd, 2012. Wadern: Schloss Dagstuhl -- Leibniz Zentrum f\"ur Informatik (ISBN 978-3-939897-35-4). LIPICS -- Leibniz International Proceedings in Informatics 14, 206-217, electronic only (2012).} \itemab Summary: Finding edge-disjoint odd cycles is one of the most important problems in graph theory, graph algorithms and combinatorial optimization. In fact, it is closely related to the well-known max-cut problem. One of the difficulties of this problem is that the Erd\"os-P\'osa 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 edge-disjoint $k$ odd cycles or there exists an edge set $F \subseteq E$ with $|F| \leq f(k)$ such that $G-F$ is bipartite. We note that the 4-edge-connectivity is best possible in this statement. 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 $\varepsilon > 0$, if $k = O ((\log \log \log n)^{1/2-\varepsilon})$, then the edge-disjoint $k$ odd cycle packing in $G$ can be solved in polynomial time of $n$. \itemrv{~} \itemcc{} \itemut{odd-cycles; disjoint paths problem; Erd\H{o}s-P\'osa property; packing algorithm; 4-edge-connectivity} \itemli{doi:10.4230/LIPIcs.STACS.2012.206} \end