Min-max relations for odd cycles in planar graphs

DOI10.1137/110845835zbMATH Open1256.05119arXiv1108.4281OpenAlexW2593107672WikidataQ57601385 ScholiaQ57601385MaRDI QIDQ4899031FDOQ4899031

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)

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].

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

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

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)

Cited In (7)

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

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)