Min-max relations for odd cycles in planar graphs

DOI10.1137/110845835MaRDI QIDQ4899031zbMATH OpenOpenAlexWikidataFDO

Authors Jean-Sébastien Sereni, Ladislav Stacho, Daniel Král'

Publication date 4 January 2013

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1108.4281

zbMATH Keywords

planar graphsT-joinsErdős-Pósa propertyodd cycle transversals

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38)

Abstract: Let m(G) be the maximum number of vertex-disjoint odd cycles of a graph G and t(G) the minimum number of vertices whose removal makes G bipartite. We show that t(G)<=6m(G) if G is planar. This improves the previous bound t(G)<=10m(G) by Fiorini, Hardy, Reed and Vetta [Math. Program. Ser. B 110 (2007), 71-91].

Recommendations

• Edge-disjoint odd cycles in planar graphs.
• Approximate min-max relations for odd cycles in planar graphs
• Approximate Min-max Relations for Odd Cycles in Planar Graphs
• Approximate min-max relations on plane graphs
• Optimal packings of edge-disjoint odd cycles

Cited in

(7)

• Approximate min-max relations on plane graphs
• Approximate Min-max Relations for Odd Cycles in Planar Graphs
• Minimum number of edges that occur in odd cycles
• Packing and covering odd cycles in cubic plane graphs with small faces
• Optimal packings of edge-disjoint odd cycles
• Negative circles in signed graphs: a problem collection
• Negative (and positive) circles in signed graphs: a problem collection

This page was built for publication: Min-max relations for odd cycles in planar graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4899031)