Graphs with no induced $K_{2,t}$

Abstract

Consider a graph $G$ on $n$ vertices with $\alpha \left(\genfrac{}{}{0ex}{}{n}{2}\right)$ edges which does not contain an induced $K_{2,t}$ ($t⩾2$). How large does $\alpha$ have to be to ensure that $G$ contains, say, a large clique or some fixed subgraph $H$? We give results for two regimes: for $\alpha$ bounded away from zero and for $\alpha =o(1)$. Our results for $\alpha =o(1)$ are strongly related to the Induced Turán numbers which were recently introduced by Loh, Tait, Timmons and Zhou. For $\alpha$ bounded away from zero, our results can be seen as a generalisation of a result of Gyárfás, Hubenko and Solymosi and more recently Holmsen (whose argument inspired ours).

8 pages; final version incorporating changes suggested by referees; new result in last section