Discrete Math Seminar: Ladislav Stacho

  • Date: 01/24/2012
  • Time: 14:30
Ladislav Stacho

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.

Other Information: 

For more information please visit SFU Mathematics Department