Publication details
MIN-MAX RELATIONS FOR ODD CYCLES IN PLANAR GRAPHS
| Authors | |
|---|---|
| Year of publication | 2012 |
| Type | Article in Periodical |
| Magazine / Source | SIAM Journal on Discrete Mathematics |
| Citation | |
| Doi | http://dx.doi.org/10.1137/110845835 |
| Keywords | Erdos-Posa property; planar graphs; odd cycle transversals; T-joins |
| Description | Let nu(G) be the maximum number of vertex-disjoint odd cycles of a graph G and tau(G) the minimum number of vertices whose removal makes G bipartite. We show that tau(G) <= 6 nu(G) if G is planar. This improves the previous bound tau(G) <= 10 nu(G) by Fiorini et al. [Math. Program. Ser. B, 110 (2007), pp. 71-91]. |