Dense induced bipartite subgraphs in triangle-free graphs

Abstract

The problem of finding dense induced bipartite subgraphs in $H$-free graphs has a long history, and was posed 30 years ago by Erdős, Faudree, Pach and Spencer. In this paper, we obtain several results in this direction. First we prove that any $K_t$-free graph with minimum degree at least $d$ contains an induced bipartite subgraph of minimum degree at least $c_t\log d/\log \log d$, confirming (asymptotically) several conjectures by Esperet, Kang and Thomassé. Complementing this result, we further obtain optimal bounds for this problem in the case of dense triangle-free graphs, and we also answer a question of Erdős, Janson, Łuczak and Spencer.

17 pages, final version to appear in Combinatorica