If G is a graph containing no loops or multiple edges, then the edge-chromatic number $X_e(C)$ of G is defined to be the least number of colours needed to colour the edges of G in such a way that no two adjacent edges have the same colour.

How to find edge-chromatic number :

1)Complete Graph($K_n$)

[I know $k_n$ is (n-1)regular and if n is even then edge-chromatic number of $k_n$ is n-1 and if n is odd then edge-chromatic number of $k_n$ is n,but how to prove it??]


  • 3
    $\begingroup$ In case you're not yet aware of the practice of accepting answers, please see this faq thread. $\endgroup$ – joriki Nov 1 '12 at 9:22
  • 1
    $\begingroup$ Also, it seems unlikely that you don't have at least some rudimentary thoughts of your own on at least part 4) of the problem -- answers will be much more useful if you point out specifically what you already understand and what's causing you trouble. $\endgroup$ – joriki Nov 1 '12 at 9:26

For a complete graph with an even number of vertices, this amounts to finding a 1-factorisation, such as the following:

Example (Source: David Eppstein via Wikimedia)

A general construction is formed by rotating a "starter", such as the following:

1-factorisation starter for $K_{18}$

Each rotation describes where to place the edges of a single colour. Picture source:

Mendelsohn and Rosa, One-factorizations of the complete graph—A survey, Journal of Graph Theory 9 (1985) 43–65. (link)

See also the above reference for further details on how to construct 1-factorisations of $K_{2n}$ and near 1-factorisations of $K_{2n-1}$. Hence

Observation: The edge-chromatic number of $K_{2n}$ is $2n-1$ (its maximum degree) for $n \geq 1$.

For $K_{2n-1}$, we simply start with a 1-factorisation of $K_{2n}$ and delete a vertex, which results in $2n-1$ distinct edge colours. This is the best possible, since each edge colour can occur at most $n-1$ times (without having adjacent monochromatic edges), so we need at least $$\frac{{2n-1} \choose 2}{n-1}=2n-1$$ colours.

Observation: The edge-chromatic number of $K_{2n-1}$ is $2n-1$ for $n \geq 2$.


Just to add to the last part of Douglas' proof in Answer 1 ... another way to see that $K_{2n-1}$ is not ($2n-2$)-edge colorable is that if it were, then each set of monochromatic edges in the coloring would have to form a perfect matching, which is impossible in a graph with an odd number of vertices.


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.