Highly connected graphs have highly connected spanning bipartite subgraphs
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866913279377408000 |
|---|---|
| author | Yuster, Raphael |
| author_facet | Yuster, Raphael |
| contents | For integers $k,n$ with $1 \le k \le n/2$, let $f(k,n)$ be the smallest integer $t$ such that every $t$-connected $n$-vertex graph has a spanning bipartite $k$-connected subgraph. A conjecture of Thomassen asserts that $f(k,n)$ is upper bounded by some function of $k$. The best upper bound for $f(k,n)$ is by Delcourt and Ferber who proved that $f(k,n) \le 10^{10}k^3 \log n$. Here it is proved that $f(k,n) \le 22k^2 \log n$. For larger $k$, stronger bounds hold. In the linear regime, it is proved that for any $0 < c < \frac{1}{2}$ and all sufficiently large $n$, if $k=\lfloor cn \rfloor$, then $f(k, n) \le 30\sqrt{c} n \le 30\sqrt{n(k+1)}$. In the polynomial regime, it is proved that for any $\frac{1}{3} \le α< 1$ and all sufficiently large $n$, if $k = \lfloor n^α\rfloor$, then $f(k ,n) \le 9n^{(1+α)/2} \le 9\sqrt{n(k+1)}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_15599 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Highly connected graphs have highly connected spanning bipartite subgraphs Yuster, Raphael Combinatorics 05C35, 05C40 For integers $k,n$ with $1 \le k \le n/2$, let $f(k,n)$ be the smallest integer $t$ such that every $t$-connected $n$-vertex graph has a spanning bipartite $k$-connected subgraph. A conjecture of Thomassen asserts that $f(k,n)$ is upper bounded by some function of $k$. The best upper bound for $f(k,n)$ is by Delcourt and Ferber who proved that $f(k,n) \le 10^{10}k^3 \log n$. Here it is proved that $f(k,n) \le 22k^2 \log n$. For larger $k$, stronger bounds hold. In the linear regime, it is proved that for any $0 < c < \frac{1}{2}$ and all sufficiently large $n$, if $k=\lfloor cn \rfloor$, then $f(k, n) \le 30\sqrt{c} n \le 30\sqrt{n(k+1)}$. In the polynomial regime, it is proved that for any $\frac{1}{3} \le α< 1$ and all sufficiently large $n$, if $k = \lfloor n^α\rfloor$, then $f(k ,n) \le 9n^{(1+α)/2} \le 9\sqrt{n(k+1)}$. |
| title | Highly connected graphs have highly connected spanning bipartite subgraphs |
| topic | Combinatorics 05C35, 05C40 |
| url | https://arxiv.org/abs/2403.15599 |