  In a simple, undirected graph G, an edge 2-coloring is a coloring of the
edges such that no vertex is incident to edges with more than 2 distinct
colors. The problem maximum edge 2-coloring (ME2C) is to find an edge
2-coloring in a graph G with the goal to maximize the number of colors. For a
relevant graph class, ME2C models anti-Ramsey numbers and it was considered in
network applications. For the problem a 2-approximation algorithm is known, and
if the input graph has a perfect matching, the same algorithm has been shown to
have a performance guarantee of 5/3. It is known that ME2C is APX-hard and that
it is UG-hard to obtain an approximation ratio better than 1.5. We show that if
the input graph has a perfect matching, there is a polynomial time
1.625-approximation and if the graph is claw-free or if the maximum degree of
the input graph is at most three (i.e., the graph is subcubic), there is a
polynomial time 1.5-approximation algorithm for ME2C
