Search

A graph G = (V, E) of order n is said to be arbitrarily partitionable if for each sequence λ = (λ1, λ2, …, λp) of positive integers with λ1 +·…·+λp = n, there exists a partition (V1, V2, …, Vp) of the vertex set V such that Vi induces a connected subgraph of order λi in G for each i ∈ {1, 2, …, p}. In this paper, we show that a threshold graph is arbitrarily partitionable if and only if it admits a perfect matching or a near perfect matching. We also give a necessary and sufficient condition for a {2K2, C4}-free graph being arbitrarily partitionable, as an extension for a result of Broersma, Kratsch and Woeginger [Fully decomposable split graphs, European J. Combin. 34 (2013) 567–575] on split graphs.