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?

Improve this question
$\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$
    – Rick Decker
    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

Reset to default
3
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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