Edge-disjoint odd cycles in planar graphs

摘要

We prove tau(odd)(G)less than or equal to2nu(odd)(G) for each planar graph G where nu(odd)(G) is the maximum number of edge-disjoint odd cycles and tau(odd)(G) is the minimum number of edges whose removal makes G bipartite, i.e. which meet all the odd cycles. For each k, there is a 3-connected planar graph G(k) with tau(odd)(G(k)) = 2k and nu(odd)(G(k)) = k. (C) 2003 Elsevier Inc. All rights reserved. [References: 20]