# 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$. Feb 7, 2014 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. Feb 7, 2014 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. Feb 7, 2014 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. Feb 8, 2014 at 20:19
• @triomphe No, I'm saying that greedy coloring isn't guaranteed to produce an optimal coloring. Feb 9, 2014 at 3:41

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