# Edge colouring and Vizing's theorem

Definition 8..1 (Edge colouring)

A -edge colouring of a graph is a function such that incident edges receive different colours.

Definition 8..2 (Edge chromatic number, chromatic index)

Given a graph , the edge chromatic number or chromatic index is the least for which is -edge-colourable.

Certainly .

Theorem 8..3 (Vizing)

Proof. The lower bound is trivial. For the upper bound we do induction on the number of edges.

Suppose we have a colouring of all but one edge using colours . Then we wish to recolour so all the edges are coloured.

Note that one colour is unused (missing'') at every vertex.

Let be the uncoloured edge. We construct a sequence of edges and a sequence of colours as follows.

Pick to be a colour missing at . Let be an edge with colour . We stop with when either is a colour unused at , or is already used on for .

If was a colour unused at then we recolour with for . This finishes the easy case where we can recolour the edges touching to give a a colouring for .

Otherwise we recolour with for and uncolour . Notice that (red) is missing at both and . Let blue be a colour unused at .

1. If red is missing at , we colour red.

2. If blue is missing at we colour blue.

3. If blue is missing at we colour with for and colour blue. (None of the , are red or blue.)

If none of the above hold, then we consider the subgraph of red and blue edges. The components of this subgraph are paths or cycles. The vertices are the end vertices of paths. Therefore they cannot all belong to the same component.

Select a component that contains exactly one of these vertices. Now swap over red and blue in this component. Now one of the conditions above must apply.

Theorem 8..4 (Edge chromatic number of a bipartite graph)

If is bipartite, then .

Proof. We embed in a -regular bipartite multi-graph as follows: We replace by two copies of and for , the copies of , we join to with parallel edges. This creates a bipartite multi-graph with vertex classes and if and were the original vertex classes in .

Now we prove the theorem for -regular bipartite multi-graphs by induction on .

Clearly true for .

Let be an edge of , Delete the vertices and . Because and were in different vertex classes, it is possible to add fewer than new edges to make a new -regular bipartite multi-graph . Now we colour by the induction hypothesis. Certainly not all the colours were used to colour the new edges. Let red be one of these colours. Certainly the red edges in with form a -factor in . Deleting this -factor gives a -regular bipartite multigraph .

Now colour by the induction hypothesis, then add the -factor back, to obtain a colouring of .

Definition 8..5 (List colouring, -choosable)

Let finite subsets of , so that each vertex has a paint box'' . We say that is -choosable if such that and is a vertex colouring.

Definition 8..6 (-choosable)

We say that is -choosable if is -choosable whenever , .

Clearly if is -choosable it is -choosable. However it is not necessarily true that if is -choosable it is -colourable.

Definition 8..7 (List chromatic number )

The list chromatic number of a graph is the least such that is -choosable.

John Fremlin 2010-02-17