On large bipartite subgraphs in dense Hfree graphs
On large bipartite subgraphs in dense Hfree graphs

Bernard Lidický, Iowa State
Fine Hall 224
A longstanding conjecture of Erdős states that any nvertex trianglefree 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 Hfree graph for a general graph H. By generalizing a result of Sudakov for 4colorable graphs H, we show that if H is 6colorable 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 5partite 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. MartinsLopez, S. Norin and J. Volec.