Return to Revisions

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.