### On large multipartite subgraphs of H-free graphs

- Series
- Combinatorics Seminar
- Time
- Thursday, March 29, 2018 - 13:30 for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- Jan Volec – McGill

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+O(n) edges. In the case of H=K_6, we actually prove the exact bound
4n^2/25 and show that this amount is needed only in the case G 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 a joint work with P. Hu, B. Lidický, T. Martins-Lopez and S. Norin.