Highly connected graphs have highly connected spanning bipartite subgraphs (Q6131741)

Summary: For integers \(k\), \(n\) with \(1 \leqslant k \leqslant 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 \textit{C. Thomassen} [J. Comb. Theory, Ser. B 35, 129--141 (1983; Zbl 0537.05034)] asserts that \(f(k, n)\) is upper bounded by some function of \(k\). The best upper bound for \(f(k, n)\) is by \textit{M. Delcourt} and \textit{A. Ferber} [Electron. J. Comb. 22, No. 3, Research Paper P3.2, 8 p. (2015; Zbl 1327.05133)] who proved that \(f(k, n) \leqslant 10^{10}k^3 \log n\). Here it is proved that \(f(k, n) \leqslant 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) \leqslant 30\sqrt{c}n\leqslant 30\sqrt{n(k+1)}\). In the polynomial regime, it is proved that for any \(\frac{1}{3} \leqslant \alpha < 1\) and all sufficiently large \(n\), if \(k=\lfloor n^\alpha \rfloor\), then \(f(k,n) \leqslant 9n^{(1+\alpha)/2}\leqslant 9\sqrt{n(k+1)}\).