This can be solved in polynomial time for any graph, as it can be converted to a [MinCut problem][1]. Just connect all red vertices into a single vertex $s$, and all blue vertices into another single vertex $t$, obtaining a multigraph (or if you prefer, a graph with edge weights). The Minimum cut in this new graph between $s$ and $t$ gives the partition that gives the coloring maximizing the number of the monochromatic edges.


  [1]: https://en.wikipedia.org/wiki/Minimum_cut