Complexity of relaxed edge colouring

Question

A (proper) $k$-edge colouring of a graph $G(V,E)$ is a function $f:E\to\{1,2,\dots,k\}$ such that adjacent vertices are mapped to different colours; that is, $f(e)\neq f(e')$ if $e$ and $e'$ are incident on the same vertex. It is known that the minimum number of colours required for edge colouring is between $\Delta(G)$ and $\Delta(G)+1$, and yet it is NP-complete to distinguish between the two cases.

Let us define a relaxed $k$-edge colouring of $G$ as a function $f:E\to\{1,2,\dots,k\}$ such that for every vertex $v$ of $G$, at most two edges incident on $v$ have the same colour.
What is the complexity of relaxed edge colouring?
I am particularly interested in the complexity of relaxed $k$-edge colouring for graphs of maximum degree $k$.

Edit: The part below was part of the question earlier. But, it is wrong because proper $k$-edge colouring and thus relaxed $k$-edge colouring are trivially in P for graphs with maximum degree $k-1$.

I am particularly interested in the complexity of relaxed $k$-edge colouring for graphs of maximum degree $k-1$. I have a hunch the problem is going to be computationally hard, which is interesting because $k$-edge colouring is polynomial time solvable for the class.

Answer 1

If $G$ is $2k$-regular, then a relaxed edge coloring with exactly $k$ colors is the same thing as a 2-factorization, and is known to always exist by results of Petersen 1891.

Otherwise, let $k=\lceil\Delta/2\rceil$ where $\Delta$ is the maximum degree of $G$. Then obviously, at least $k$ colors are needed in any relaxed coloring of $G$. But $G$ can be augmented to a $2k$-regular graph $G'$ (by adding extra vertices and edges if necessary) and any 2-factorization of $G'$ restricts to a relaxed edge coloring of $G$.

So relaxed edge coloring is easy: the optimal number of colors is always $\lceil\Delta/2\rceil$.