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$).
(Copied from a comment:)
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 &quot;maximum k-cut&quot; and also &quot;maximum k-colorable subgraph&quot;.