A linear bound for a connectivity partition in graphs

Kühn and Osthus proved that, for every positive integer $\mathrm{\ell }$, every $2^{16}{\mathrm{\ell }}^2$-connected graph $G$ has a partition $V(G)=S\cup T$ such that $G[S]$ and $G[T]$ are $\mathrm{\ell }$-connected and $d_T(v)\ge \mathrm{\ell }$ for every $v\in S$. And they asked whether the quadratic bound can be replaced by a linear bound. In this paper, we answer this question in the affirmative by proving that every $641\mathrm{\ell }$-connected graph $G$ has a partition $V(G)=S\cup T$ such that $G[S]$ and $G[T]$ are $\mathrm{\ell }$-connected and $d_T(v)\ge \mathrm{\ell }$ for every $v\in S$. The proof integrates the Moser-Tardos resampling algorithm.