Edge colouring and Vizing's theorem

Definition 8..1 (Edge colouring)  

A $k$-edge colouring of a graph $G$ is a function $c: E(G) \mapsto \{ 1,2, \cdots, k \}$ such that incident edges receive different colours.

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

Given a graph $G$, the edge chromatic number or chromatic index $\chi'(G)$ is the least $k$ for which $G$ is $k$-edge-colourable.

Certainly $\Delta(G) \le \chi'(G)$.

Theorem 8..3 (Vizing)  

$\Delta(G) \le \chi'(G) \le \Delta(G) + 1$

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 $xy \in E(G)$ using colours $\{ 1,2,\cdots,\Delta(G) + 1 \}$. Then we wish to recolour so all the edges are coloured.

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

Let $x y_0$ be the uncoloured edge. We construct a sequence of edges $x y_0, x y_1, \cdots$ and a sequence of colours $c_0, c_1, \cdots$ as follows.

Pick $c_i$ to be a colour missing at $y_i$. Let $x y_{i+1}$ be an edge with colour $c_i$. We stop with $k = i$ when either $c_k$ is a colour unused at $x$, or $c_k$ is already used on $x y_j$ for $j < k$.

If $c_k$ was a colour unused at $x$ then we recolour $x y_i$ with $c_i$ for $0 \le i \le k$. This finishes the easy case where we can recolour the edges touching $x$ to give a a colouring for $G$.

Otherwise we recolour $x y_i$ with $c_i$ for $0 \le i < j$ and uncolour $x y_j$. Notice that $c_k$ (red) is missing at both $y_j$ and $y_k$. Let blue be a colour unused at $x$.

1. If red is missing at $x$, we colour $x y_j$ red.

2. If blue is missing at $y_j$ we colour $x y_j$ blue.

3. If blue is missing at $y_k$ we colour $x y_i$ with $c_i$ for $j \le i < k$ and colour $x y_k$ blue. (None of the $x y_i$, $j \le i < k$ 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 $x,y_i,y_k$ 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.

$\qedsymbol$

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

If $G$ is bipartite, then $\chi'(G) = \Delta(G)$.

Proof. We embed $G$ in a $\Delta(G)$-regular bipartite multi-graph as follows: We replace $G$ by two copies of $G$ and for $v',v''$, the copies of $v \in V(G)$, we join $v'$ to $v''$ with $\Delta(G) - d_G(v)$ parallel edges. This creates a bipartite multi-graph $H$ with vertex classes $(X' \bigcup Y'')$ and $(Y' \bigcup X'')$ if $X$ and $Y$ were the original vertex classes in $G$.

Now we prove the theorem for $\Delta$-regular bipartite multi-graphs $H$ by induction on $\left\Vert H\right\Vert + \Delta(H)$.

Clearly true for $\Delta(H) = 1$.

Let $uv$ be an edge of $H$, Delete the vertices $u$ and $v$. Because $u$ and $v$ were in different vertex classes, it is possible to add fewer than $\Delta$ new edges to make a new $\Delta$-regular bipartite multi-graph $H'$. Now we colour $H'$ 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 $H'$ with $uv$ form a $1$-factor in $G$. Deleting this $1$-factor gives a $(\Delta-1)$-regular bipartite multigraph $H''$.

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

$\qedsymbol$

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

Let $L : V(G) \mapsto \{$ finite subsets of $\mathbb{N}$ $\}$, so that each vertex $v$ has a ``paint box'' $L(v)$. We say that $G$ is $L$-choosable if $\exists c: V(G) \mapsto \mathbb{N}$ such that $c(v) \in L(v)$ $\forall v$ and $c$ is a vertex colouring.

Definition 8..6 ($k$-choosable)  

We say that $G$ is $k$-choosable if $G$ is $L$-choosable whenever $\left\Vert L(v)\right\Vert = k$, $\forall v \in V(G)$.

Clearly if $G$ is $k$-choosable it is $k+1$-choosable. However it is not necessarily true that if $G$ is $k$-choosable it is $k$-colourable.

Definition 8..7 (List chromatic number $\chi_l(G)$)  

The list chromatic number $\chi_l(G)$ of a graph $G$ is the least $k$ such that $G$ is $k$-choosable.