Highly connected graphs have highly connected spanning bipartite subgraphs

Abstract

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 \alpha <1$ and all sufficiently large $n$, if $k=\lfloor n^{\alpha }\rfloor$, then $f(k,n)\le 9n^{(1+\alpha )/2}\le 9\sqrt{n(k+1)}$.

References in corpus (1)

• Large subgraphs without short cycles