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$).