Discrete Math Seminar: Ladislav Stacho
- Date: 01/24/2012
- Time: 14:30
Simon Fraser University
Min-max relations for odd cycles in planar graphs
Let ne(G) be the maximum number of vertex-disjoint odd cycles of a graph G and ta(G) the minimum number of vertices whose removal makes G bipartite. We show that ta(G) ≤ 6ne(G) if G is planar. This improves the previous bound ta(G) ≤ 10ne(G) by Fiorini, Hardy, Reed and Vetta
[Math. Program. Ser. B 110 (2007), 71–91]. In the talk, we will discuss background of the problem and sketch some proof techniques of our result.
This is a joint work with Daniel Kral and Jean-Sebastien Sereni.
For more information please visit SFU Mathematics Department