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.
Best Answer
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.