Bollobás‐Erdős‐Tuza Conjecture for Graphs With No Induced Ks,t

ABSTRACT A widely open conjecture proposed by Bollobás, Erdős, and Tuza in the early 1990s states that for any ‐vertex graph , if the independence number , then there is a subset with such that intersects all maximum independent sets of . In this study, we prove that this conjecture holds for graphs that do not contain an induced for fixed . Our proof leverages the probabilistic method at an appropriate juncture.