What is the complexity of this edge coloring problem? Recently, I have encountered the following variant of edge coloring.


  Given a connected undirected graph, find a coloring of the edges that uses the maximum number of colors while also satisfying the constraint that, for every vertex $v$, the edges incident to $v$ use at most two colors.


My first guess is that the problem is NP-hard. Classical NP-hard proofs for graph coloring problems are mostly by reduction from 3SAT. But in my opinion, these proofs are not useful for this problem because edges incident to a vertex can be colored with the same color, so we cannot construct logic components in the graph.

Could this problem be NP-hard? If yes, what is a proof? If we cannot fine a proof, is there any method to determine the complexity of this problem?

Thanks!
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.