2
$\begingroup$

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!

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.