Discrete Math Seminar: Ladislav Stacho

Abstract:

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.