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$)

Solution 1:

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$.

Solution 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.