Skip to main content
edited body
Source Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

Yes, for all $n$, the edge-chromatic number of $K_{2n}$ is $2n-1$ and the edge chromatic-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.

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.

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.

Source Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

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.