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?

  • 3
    $\begingroup$ 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$. $\endgroup$ – G. Bach Feb 7 '14 at 17:54
  • $\begingroup$ @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. $\endgroup$ – Rick Decker Feb 7 '14 at 22:46
  • $\begingroup$ @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. $\endgroup$ – G. Bach Feb 7 '14 at 23:33
  • 1
    $\begingroup$ @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. $\endgroup$ – G. Bach Feb 8 '14 at 20:19
  • 1
    $\begingroup$ @triomphe No, I'm saying that greedy coloring isn't guaranteed to produce an optimal coloring. $\endgroup$ – G. Bach Feb 9 '14 at 3:41

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

  • 1
    $\begingroup$ More generally, it is a special case of MAX-CSP, where only inequality constraints are allowed. $\endgroup$ – Yuval Filmus Mar 4 '14 at 5:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.