Publication details
Edge-disjoint odd cycles in planar graphs
| Authors | |
|---|---|
| Year of publication | 2004 |
| Type | Article in Periodical |
| Magazine / Source | JOURNAL OF COMBINATORIAL THEORY SERIES B |
| Citation | |
| Doi | http://dx.doi.org/10.1016/S0095-8956(03)00078-9 |
| Keywords | bipartite graphs; odd cycles; planar graphs; Erfos-Posa property |
| Description | 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. |