The problem is defined here but for completeness I'm copying it below:
Given a graph $G=(V,E)$ and a weight function $w: E \rightarrow N$, find a k-partition (coloring) of vertices such that the total weight of the monochromatic edges (i.e. those that connect same-color vertices) is minimized:
$min \sum_{(v_1, v_2)\in E , c(v_1)=c(v_2)} w(v_1, v_2)$
where $c$ denotes a k-partitioning or k-coloring, $c: V \rightarrow [1 \dots k]$
My question: Is this problem NP-complete or NP-hard? and any references for this problem?
