Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | https://arxiv.org/abs/2405.18264 |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916334790508544 |
|---|---|
| author | Cheng, Xinbu Xu, Zixiang |
| author_facet | Cheng, Xinbu Xu, Zixiang |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_18264 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Bollobás-Erdős-Tuza conjecture for graphs with no induced $K_{s,t}$ Cheng, Xinbu Xu, Zixiang Combinatorics 05C69 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. |
| title | Bollobás-Erdős-Tuza conjecture for graphs with no induced $K_{s,t}$ |
| topic | Combinatorics 05C69 |
| url | https://arxiv.org/abs/2405.18264 |