# For which values of $m$ is $m$-partition hard?

Consider the following reduction: $$m$$-colouring to $$m$$-partition.

Define an $$m$$-partition as: Given an undirected graph $$G = (V, E)$$ and an integer $$j$$. Does there exist a partition of the vertices into $$m$$ parts $$\{V_1, V_2, \ldots , V_m\}$$ such that at least $$j$$ of the edges have their endpoints in different parts of the partition?

I was able to come up with the reduction, but now I'm stuck at this question:

What I need to find is the values of $$m$$ where the reduction implies that $$m$$-Partition is NP-complete?

• For what values of m is m-coloring NP-complete? What research have you done on that? – D.W. Apr 26 at 7:17
• @Matthew Not quite: the problem is still NP-complete for 4 colors. When you say "a map" you mean a planar graph and that's true, but in general it's still hard. – Juho Apr 26 at 9:14
• @Matthew No, consider the complete graph on 5 vertices, or more generally any graph with a large clique. – Juho Apr 27 at 4:34
• @Matthew To blow your mind even more, they are not the same problems. A graph without a large clique can still require a lot of colors :-) Have a look at the Mycielskians. – Juho Apr 27 at 8:09
• @Matthew Do as many exercises as you can, there's no substitute for that. Play around with graphs and reductions and you will improve over time. I don't have a particular resource in mind - there's a lot of books and other material that is good. – Juho Apr 28 at 7:18

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 > 2$$, the $$m$$-partition problem is NP-complete by reduction from $$m$$-coloring, which is NP-complete for that range of $$m$$.