1
$\begingroup$

Edge coloring of a graph is an assignment of “colors” to the edges of the graph so that no two adjacent edges have the same color with an optimal number of colors. Two edges are said to be adjacent if they are connected to the same vertex.

There is no known polynomial time algorithm for edge-coloring every graph with an optimal number of colors. Nevertheless, is there any efficient algorithm for edge-coloring every complete graph with an optimal number of colors? I bielieve this exits but I cannot find any source for this.

$\endgroup$

1 Answer 1

4
$\begingroup$

Yes, for all $n$, the edge-chromatic number of $K_{2n}$ is $2n-1$ and the edge-chromatic number of $K_{2n+1}$ is $2n+1$. Moreover, it is easy to construct such edge-colourings in polynomial time. For example, see this Wikipedia page for an easy method to construct a "$1$-factorization" of $K_{2n}$. An optimal edge-colouring for $K_{2n+1}$ can be obtained by applying this method to $K_{2n+2}$, and then deleting the edges incident to the extra vertex.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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