A variation of the graph coloring problem

Given a set of colors $M$ and a graph $G=(V,E)$. Allocate the colors to minimize the number edges with same color on the two vertices of the edge (i.e. minimize pairs of adjoining vertices with same color.).

This problem is different from standard coloring problem. Could someone please provide some literature where this problem is studied?

• This is at least as hard as the graph coloring problem since a graph admits a $k$-coloring iff it can be colored with $k$ colors such that the number of adjacent vertices with the same color is $0$. – G. Bach Feb 7 '14 at 17:54
• @G.Bach. That said, I'd be interested in seeing an algorithm. Right now it's late and I'm hungry, so I might be missing an obvious solution. – Rick Decker Feb 7 '14 at 22:46
• @RickDecker Naive approach would probably be binary search over $\{1,...,n\}$ colors, where for each $k \in \{1,...,n\}$ we check whether there is a $k$-coloring. – G. Bach Feb 7 '14 at 23:33
• @triomphe Assuming we can solve your problem in polynomial time, then we could use that solution to solve the graph coloring problem ("does $G$ admit a $k$-coloring?") in polynomial time by checking whether $G$ can be colored using $M = [k]$ with $0$ conflicts. – G. Bach Feb 8 '14 at 20:19
• @triomphe No, I'm saying that greedy coloring isn't guaranteed to produce an optimal coloring. – G. Bach Feb 9 '14 at 3:41

If $|M| = 2$, this is the max-cut problem.