Highly Connected Graphs Have Highly Connected Spanning Bipartite Subgraphs

For integers $k,n$ with 1 ≤ k ≤ 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) ≤ 10¹⁰k³ log n. Here it is proved that f(k,n) ≤ 22k² log n. For larger k, stronger bounds hold. In the linear regime, it is proved that for any 0 < c < 1/2 and all sufficiently large n, if k= cn, then f(k, n) ≤ 30√c n ≤ 30√n(k+1). In the polynomial regime, it is proved that for any 1/3 ≤ α < 1 and all sufficiently large n, if k = n^α, then f(k ,n) ≤ 9n(1+α)/2 ≤ 9√n(k+1).