5
$\begingroup$

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?

$\endgroup$
10
  • 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, 2014 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$ Feb 7, 2014 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, 2014 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, 2014 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, 2014 at 3:41

1 Answer 1

3
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ More generally, it is a special case of MAX-CSP, where only inequality constraints are allowed. $\endgroup$ Mar 4, 2014 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.