Arbitrarily Partitionable {2K₂, C₄}-Free Graphs

A graph G = (V, E) of order n is said to be arbitrarily partitionable if for each sequence λ = (λ₁, λ₂, …, λ_p) of positive integers with λ₁ + … +λ_p = n, there exists a partition (V₁, V₂, … , V_p) of the vertex set V such that V_i 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 {2K₂, C₄}-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.