Fully decomposable split graphs

We discuss various questions around partitioning a split graph into connected parts. Our main result is a polynomial time algorithm that decides whether a given split graph is fully decomposable, that is, whether it can be partitioned into connected parts of orders _α1,_α2,…,_αk${\alpha }_1,{\alpha }_2,\dots ,{\alpha }_k$ for every _α1,_α2,…,_αk${\alpha }_1,{\alpha }_2,\dots ,{\alpha }_k$ summing up to the order of the graph. In contrast, we show that the decision problem whether a given split graph can be partitioned into connected parts of orders _α1,_α2,…,_αk${\alpha }_1,{\alpha }_2,\dots ,{\alpha }_k$ for a given partition _α1,_α2,…,_αk${\alpha }_1,{\alpha }_2,\dots ,{\alpha }_k$ of the order of the graph, is NP-hard.