I have an undirected graph with weighted edges. I want to color the vertices with a given $k$ colors. Let's assume there is no proper coloring with $k$ colors such that adjacent nodes will always have different colors. I want to find the improper color assignments that would minimize the sum of weights of edges between nodes of the same color.
I have looked through many papers looking at improper coloring algorithms but cannot find this particular variant. This paper looks at something similar, but instead minimizes $k$ given a threshold on the sum of weights. Instead, I want to fix $k$ and minimize the sum of weights. Does anybody know the best approach for this?
Full citation to the paper:
J. Araujo, J.-C. Bermond, F. Giroire, F. Havet, D. Mazauric, R. Modrzejewski, Weighted improper coloring, Research report 7590, INRIA, Sophia Antipolis, 2011.