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?