For which values of $m$ is $m$-partition hard?
The $1$-partition problem is trivial, since there is only one possible partition.

The $2$-partition problem is the same as MAX-CUT, which is known to be NP-complete.

For $m &gt; 2$, the $m$-partition problem is NP-complete by reduction from $m$-coloring, which is NP-complete for that range of $m$.