# Solve Max 3 color problem using 3 color decision problem

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?

• Sorry, but what is "max 3 colorability"? – Juho Dec 1 '17 at 7:55
• 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? – 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.