تقرير
Bollob\'{a}s-Erd\H{o}s-Tuza conjecture for graphs with no induced $K_{s,t}$
| العنوان: | Bollob\'{a}s-Erd\H{o}s-Tuza conjecture for graphs with no induced $K_{s,t}$ |
|---|---|
| المؤلفون: | Cheng, Xinbu, Xu, Zixiang |
| سنة النشر: | 2024 |
| المجموعة: | Mathematics |
| مصطلحات موضوعية: | Mathematics - Combinatorics, 05C69 |
| الوصف: | A widely open conjecture proposed by Bollob\'as, Erd\H{o}s, and Tuza in the early 1990s states that for any $n$-vertex graph $G$, if the independence number $\alpha(G) = \Omega(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. Comment: 5 pages |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2405.18264 |
| رقم الأكسشن: | edsarx.2405.18264 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |