What is the complexity of a special multigraph edge coloring problem

Question

Given a multigraph such that there are 0 or 2 edges connecting every two vertices, we are to color the edges of this graph so that adjacent edges receive distinct colors. It is known that we need at least $\Delta(G)$ colors, and $\Delta(G)+2$ colors are sufficient, so its chromatic index is $\Delta(G)$, or $\Delta(G)+1$, or $\Delta(G)+2$. What is the complexity of determining the chromatic index of such a graph $G$? I guess it might be NP-Complete but is there any source mentioning this result? Thanks in advence!

Answer 1

I strongly suspect that this is NP-complete, but the approach I have in mind does not seem to work! I wanted to use the the well-known fact that it is NP-complete to decide whether the chromatic index $\chi'(G)$ of a (simple) cubic graph $G$ is $3$ or $4$ (see this paper of Holyer).

For the reduction, start with a simple cubic graph $G$ and double each edge to obtain a multigraph $2G$.

False Claim. $\chi'(2G)=6$ if and only if $\chi'(G)=3$.

To refute the false claim, let $P$ be the Petersen graph. It is well-known that $\chi'(P)=4$, but it is easy to check that $\chi'(2P)=6$.

If the false claim were true, then a polynomial-time algorithm to compute $\chi'(2G)$ would yield a polynomial-time algorithm to compute $\chi'(G)$.

Unfortunately, it might be necessary to use the gadgets from Holyer's reduction for a direct reduction from 3-SAT.