Graph coloring decision problem NP-complete
A simpler reduction is from MAX-CUT. The idea is to represent each edge as a gadget which is a complete bipartite graph having $N$ vertices on each side. By choosing $N$ large enough, we can force any potential coloring to color all vertices on one side using color 1, and all vertices on the other side using color 2. You can now connect these gadgets in such a way that the maximum number of bichromatic edges is closely related to the maximum cut in the original graph.

I'll let you work out the details.