A Polynomial Characterization of Some Graph Partitioning Problems