Graphs with no induced K-2,K-t

Abstract

Consider a graph G on n vertices with αn 2 edges which does not contain an induced K2,t (t > 2). How large must α be to ensure that G contains, say, a large clique or some fixed subgraph H? We give results for two regimes: for α bounded away from zero and for α = o(1). Our results for α = o(1) are strongly related to the Induced Tur´an numbers which were recently introduced by Loh, Tait, Timmons and Zhou. For α bounded away from zero, our results can be seen as a generalisation of a result of Gy´arf´as, Hubenko and Solymosi and more recently Holmsen (whose argument inspired ours)