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 a1,a2,…,ak for every a1,a2,…,ak 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 a1,a2,…,ak for a given partition a1,a2,…,ak of the order of the graph, is NP-hard