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 for every α1,α2,…,α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 for a given partition α1,α2,…,αk of the order of the graph, is NP-hard.