For $k \geq 1$, if a graph $G$ has $\delta(G) \geq \frac{n(G)+k-2}{2}$, then $G$ is $k$-connected. This minimum-degree condition is sharp.

What if instead of having all of $G$ be $k$-connected, it sufficed to partition $V(G)$ into (not too many!) parts, each of which induces a $k$-connected subgraph? Such a partition is $k$-proper. Such a tool could be used to help in clustering applications in social networks.

We seek a sharp minimum-degree condition that implies that $G$ has a $k$-proper partition.

Conjecture. If $\delta(G) \geq \sqrt{(k-1)n}$, then $G$ has a $k$-proper partition with at most $\frac{n-k+1}{\delta(G)-k+2}$ parts.

Ferrara et. al find that the conjecture holds for $k=2$. Also, if $\delta(G) \geq \sqrt{c(k-1)n}$, for $c = \frac{2123}{180}$, then $G$ has a $k$-proper partition into $\frac{cn}{\delta(G)}$ parts. If we relax the condition that the number of parts is bounded by a ratio of $n/\delta(G)$, then the minimum degree condition can be relaxed to $\delta(G) \geq \sqrt{\frac{193}{30}(k-1)n}$.