Approximation and hardness results for the maximum edge q-coloring problem

On the algorithmic side, we restrict to the case q=2, since this is the most important in practice and we show a 5/3-approximation algorithm for graphs which have a perfect matching.