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?
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.