I've been stumped on this question for a while and can't find a solution. How can I find the max 3 colorability of a graph(optimization problem) with 3 colorability (decision problem) without brute force searching every combinations of edges?

  • 3
    $\begingroup$ Sorry, but what is "max 3 colorability"? $\endgroup$ – Juho Dec 1 '17 at 7:55
  • 2
    $\begingroup$ One can think of two optimization variants of 3-colorability: (legally) coloring the maximal number of vertices, coloring all vertices while minimizing the number of monochromatic edges. Which one are you interested in? $\endgroup$ – Yuval Filmus Jul 30 '18 at 13:33

The problem "Can a given graph $G$ be 3-colored so that at least $m$ edges are bichromatic?" is in NP, and therefore can be reduced to 3-colorability (since 3-colorability is NP-hard). Using this, you can solve maximum 3 colorability, employing a simple binary search that invokes a 3-colorability oracle $O(\log n)$ times.

There might be a more direct reduction (which might have been the point of the question), but there is no real problem with this answer as well.


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.