On large bipartite subgraphs in dense H-free graphs

On large bipartite subgraphs in dense H-free graphs

-
Bernard Lidický, Iowa State
Fine Hall 224

A long-standing conjecture of Erdős states that any n-vertex triangle-free graph can be made bipartite by deleting at most n^2/25 edges. In this talk, we study how many edges need to be removed from an H-free graph for a general graph H. By generalizing a result of Sudakov for 4-colorable graphs H, we show that if H is 6-colorable then G can be made bipartite by deleting at most 4n^2/25 edges.

Moreover, this amount is needed only in the case G that is a complete 5-partite graph with balanced parts. As one of the steps in the proof, we use a strengthening of a result of Füredi on stable version of Turán's theorem.

This is joint work with P. Hu, T. Martins-Lopez, S. Norin and J. Volec.