Min-max relations for odd cycles in planar graphs

Abstract

We improve the known relation between the maximum number of vertex-disjoint odd cycles in a planar graph and the minimum number of vertices whose removal makes the graph bipartite. Our proof uses methods from linear programming.

Keywords

• planar graphs
• odd cycles
• transversals
• T-joins