# Name of this graph partitioning problem? (related to coloring)

Given a graph $$G=(V,E)$$ and an integer $$k$$, find a partition $$P_1, P_2, \dots, P_k$$ of $$V$$ into $$k$$ parts that minimize the total number of edges between two vertices in the same part, i.e. $$\sum_i |(P_i\times P_i)\cap E|$$.

May someone please provide the name of this problem and/or references?

If $$k$$ is larger than or equal to the chromatic number of $$G$$, then the number of edges under concern is $$0$$. But if $$k$$ is lower than the chromatic number, then it is strictly positive. Also, it is trivially bounded by $$m=|E|$$ (in the case $$k=1$$).

• If you are not interested in approximations, then you can equally well look at the question of maximizing the number of edges between different parts, and this is usually known as "maximum k-cut" and also "maximum k-colorable subgraph". Feb 28 at 21:52
• Thank you @JukkaSuomela, this seems like the answer I was looking for; please post it as an answer so I may accept it. Mar 1 at 8:53