In this work we study the testability of a family of graph partition properties that generalizes a family previously studied by Goldreich, Goldwasser, and Ron (Journal of the ACM, 1998). While the family studied by Goldreich et al. includes a variety of natural properties, such as k-colorability and containing a large cut, it does not include other properties, such as split graphs, and more generally (p,q)-colorable graphs, that should clearly be regarded as graph partition properties. The generalization we consider better captures the idea of partition properties by allowing to impose constraints on the edge-densities within and between parts (relative to the sizes of the parts). We denote the family studied in this work by $\mathcal{GPP}$.

We first show that all properties in $\mathcal{GPP}$ have a testing algorithm whose query complexity is polynomial in $1/\epsilon$, where $\epsilon$ is the given proximity parameter (and there is no dependence on the size of the graph). As the testing algorithm has two-sided error, we next address the question of which properties in $\mathcal{GPP}$ can be tested with one-sided error and query complexity polynomial in $1/\epsilon$. We answer this question by establishing a characterization result. Namely, we define a subfamily $\mathcal{GPP}_{0,1}$ of $\mathcal{GPP}$ and show that every property $P \in \mathcal{GPP}_{0,1}$ is testable by a one-sided error algorithm that has query complexity poly$(1/\epsilon)$ and that if $P \in \mathcal{GPP}\backslash\mathcal{GPP}_{0,1}$ then it cannot have a one-sided error testing algorithm whose query complexity is independent of the input graph's size.