An $O(k\log (n/k))$ Bound on Spanning Bipartite Connectivity

G. Gutin, Y. Hao, Y. Zhou

For integers $1\le k\le n/2$, let $f(k,n)$ be the least integer $s$ such that every $s$-connected graph on $n$ vertices contains a spanning bipartite $k$-connected subgraph. Thomas…