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 468/575. This improves on the previous best (trivial) ratio of 4/5.