Bollob\'{a}s-Erd{o}s-Tuza conjecture for graphs with no induced Ks,t

A widely open conjecture proposed by Bollob\'as, Erd{o}s, and Tuza in the early 1990s states that for any n-vertex graph G, if the independence number α(G) = Ω(n), then there is a subset T ⊆ V(G) with $|T| = o(n)$ such that T intersects all maximum independent sets of G. In this paper, we prove that this conjecture holds for graphs that do not contain an induced Ks,t for fixed t ≥ s. Our proof leverages the probabilistic method at an appropriate juncture.