An edge 2-coloring is a coloring of the edges of an undirected graph such that each vertex is incident to edges of at most two distinct colors. In the maximum edge 2-coloring problem, the input is an undirected graph, and the goal is to find an edge 2-coloring using the maximum possible number of colors.

The maximum edge 2-coloring problem is known to be APX-hard, and the best known approximation factor is 2. Approximation algorithms with a factor better than 2 are known only for particular classes of graphs that have a perfect matching.

In this talk, we present a 9/5-approximation algorithm for the maximum edge 2-coloring problem on bipartite graphs.