An Improved Approximation Algorithm for Maximum Edge 2-Coloring in Simple Graph(Theory of Computer Science and Its Applications)
Zhi‐Zhong Chen, Ruka Tanahashi · Institutional Repositories DataBase (IRDB) · 2007
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 $\frac{468}{5^{-}5}$ This improves on the previous best (trivial) ratio of $\frac{4}{5}$