# Optimal improper vertex-coloring of graph with weighted edges

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?

EDIT: 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.

• A good place to start might be to look at the literature for the maximum-cut problem, which (as it shouldn't be too hard to convince yourself) is the $k=2$ case of your problem: en.wikipedia.org/wiki/Maximum_cut – Gregory J. Puleo Feb 26 at 21:34
• An algorithm for the problem in the paper you linked to could be used to solve your problem as well (briefly: do a binary search on the sum of weights). But it doesn't look like the paper provides such an algorithm, in general. – Misha Lavrov Feb 27 at 2:22