























A widely open conjecture proposed by Bollobás, Erdő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 \subseteq 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 $K_{s,t}$ for fixed $t \ge s$. Our proof leverages the probabilistic method at an appropriate juncture.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。