Approximating 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 roughly 0.8420.842 and runs in O(n3m)O(n3m) time, where nn (respectively, mm) is the number of vertices (respectively, edges) in the input graph. The previously best ratio achieved by a polynomial–time approximation algorithm was 56≈0.833.