Min-max relations for odd cycles in planar graphs

Abstrakt

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.

Klíčová slova

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