What is the complexity of this edge coloring problem?
This problem is NP-hard and APX-hard; see: Adamaszek and Popa, 
Approximation and Hardness Results for the Maximum Edge $q$-coloring 
Problem, Lecture Notes in Computer Science 6507 (2010) 132-143.

The parameterized complexity aspects of this problem is addressed in this recent paper.