# Coloring Graph Problem

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??]

2)Wheel($W_n$)

• In case you're not yet aware of the practice of accepting answers, please see this faq thread. – joriki Nov 1 '12 at 9:22
• 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. – 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: A general construction is formed by rotating a "starter", such as the following: 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.