Informace o publikaci
MIN-MAX RELATIONS FOR ODD CYCLES IN PLANAR GRAPHS
| Autoři | |
|---|---|
| Rok publikování | 2012 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | SIAM Journal on Discrete Mathematics |
| Citace | |
| Doi | http://dx.doi.org/10.1137/110845835 |
| Klíčová slova | Erdos-Posa property; planar graphs; odd cycle transversals; T-joins |
| Popis | 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]. |