An improved approximation algorithm for maximum edge 2-coloring in simple graphs

We present a polynomial-time approximation algorithm for legally coloring as many edges of a given simple graph as possible using two colors. It achieves an approximation ratio of 468575. This improves on the previous best (trivial) ratio of 45.