Section 4.2 Edge Colouring
In the previous section, we focused on colourings of vertices of a graph. In the analogous problem for edges, a proper edge colouring is an assignment of colours to edges such that no two edges that share a vertex receive the same colour. The edge chromatic number \(\chi'(G)\) of \(G\) is the minimum number of colours used in a proper edge colouring of \(G\text{.}\) It is sometimes called the chromatic index of \(G\text{.}\) As it turns out, the edge chromatic number of any bipartite graph is easy to find. First, we prove the following simple lemma. Recall that the degree of a vertex \(v\) in a graph \(G\) is the number of edges incident with \(v\) and that the minimum/maximum degree among vertices in \(G\) are denoted \(\delta(G)\) and \(\Delta(G)\text{,}\) respectively. A graph \(G\) is \(k\)-regular if \(\Delta(G)=\delta(G)=k\text{.}\)
Proof.
Theorem 4.2.2. Kőnig’s Edge Colouring Theorem.
For any bipartite graph \(G\text{,}\)
\begin{equation*}
\chi'(G)=\Delta(G).
\end{equation*}
Proof.
The lower bound \(\chi'(G)\geq \Delta(G)\) is clear because every edge incident to a given vertex must receive a different colour. So, we prove the upper bound. By Lemma 4.2.1, we can assume that \(G\) is regular. We apply Exercise 10 with \(X=\emptyset\) to find a perfect matching. Colour these edges with one colour and delete them. What remains is a \((\Delta(G)-1)\)-regular bipartite graph. Repeat this until all edges have been coloured.
Edge colouring can be seen as a special case of vertex colouring via a construction known as a “line graph”. The line graph \(L(G)\) of a graph \(G\) is the graph with vertex set \(E(G)\) where two vertices of the line graph are adjacent if and only if they corresponds to edges of \(G\) that share an endpoint. We get the following nice connection between Theorem 4.2.2 and the ideas presented in Section 4.1.
Corollary 4.2.3.
Line graphs of bipartite graphs are perfect.Proof.
The chromatic number of the line graph of a graph \(G\) is precisely \(\chi'(G)\text{.}\) Also, if \(G\) is bipartite, the clique number of its line graph is \(\Delta(G)\text{.}\) So, by Theorem 4.2.2, the line graph of a bipartite graph satisfies \(\chi=\omega\text{.}\) Any induced subgraph of the line graph of \(G\) is, itself, the line graph of a subgraph of \(G\) and therefore also satisfies \(\chi=\omega\text{.}\) This completes the proof.
Now, in the realm of general (not necessarily bipartite) graphs, the equation \(\chi'(G)=\Delta(G)\) no longer holds, but it is not far from holding.
Theorem 4.2.4. Vizing’s Theorem.
For any graph \(G\text{,}\)
\begin{equation*}
\Delta(G)\leq \chi'(G)\leq \Delta(G)+1.
\end{equation*}
Proof.
Again, the bound \(\chi'(G)\geq \Delta(G)\) is trivial because the edges incident to a given vertex must receive distinct colours. So, we prove the upper bound.
We show that any graph \(G\) has an edge colouring using at most \(\Delta(G)+1\) colours by induction on \(|E(G)|\text{.}\) The base case \(|E(G)|=0\) is trivial. Now, let \(vy_1\) be any edge of \(G\) and let \(G'-G\setminus\{vy_1\}\text{.}\) By induction, the edges of \(G'\) can be coloured with \(\Delta(G)+1\) colours. Also, in any such colouring, every vertex \(u\) has at least one colour that is free at \(u\text{,}\) meaning that it is not assigned to any of its incident edges. Let red be a colour that is free at \(v\text{.}\) We insert the edge \(xy_1\) back into the graph and colour it with red.
Now, of course, this may go wrong because the colour red may not be free at \(y_1\text{.}\) However, there is another colour, say blue, which is free at \(y_1\text{.}\) Now, let \(W_1\) be the longest walk in \(G\setminus \{xy_1\}\) starting at \(y_1\) whose edge colours alternate between red and blue. Note that this walk is, in fact, a path because each vertex is incident to at most one edge of each colour and \(y_1\) is not incident to any blue edge and so the walk cannot come back to \(y_1\) either. If this walk ends at any vertex other than \(v\text{,}\) then we swap the colours of the edges along the walk to obtain a proper edge colouring and we are done. So, it ends at \(v\text{.}\) We let \(y_2\) be the penultimate vertex of the walk and note that it is adjacent to \(v\) via a blue edge. At this point, we recolour the edge \(vy_1\) to blue and the edge \(vy_2\) to red.
Now, let us explain the general situation. For some \(k\geq 1\text{,}\) assume that
- \(y_1,\dots,y_k\) are neighbours of \(v\)
- the edges \(vy_1,\dots,vy_{k-1}\) coloured with distinct colours which differ from the colour red
- the edge \(vy_{k}\) is coloured with red
- for each \(1\leq j\leq k-1\text{,}\) \(P_j\) is a path from \(v\) to \(y_{j+1}\) in which the edge colours alternate between the colour of the edge \(vy_j\) and red,
- there may be two red edges incident to \(y_k\) but, otherwise, the colouring is proper.
Now, take any colour, say green, that is free at \(y_k\text{.}\) As before, we take \(W_k\) to be a walk of maximum length starting at \(y_k\) whose edges alternate between red and green. As before, if the walk \(W_k\) does not end at \(v\text{,}\) then we swap the colours along it to get a proper edge colouring. So, it must end at \(v\text{.}\) Thus, the last edge of this walk is green. Now, we observe that this last edge cannot be one of the edges \(vy_j\) for \(1\leq j\leq k-1\) for, if it were, then both \(W_k\) and \(P_j\) alternate between red and green and if we look at the first time that they intersect, then we find a vertex which is incident to either two red edges or two green edges, which is a contradiction. Since this colour does not appear on \(vy_j\) for \(1\leq j\leq k-1\text{,}\) we have that the vertex let \(y_{k+1}\) that comes before \(v\) on \(W_k\) is distinct from \(y_1,\dots,y_k\text{.}\) We change the colour of \(vy_k\) to green, the colour of \(vy_{k+1}\) to red and obtain \(P_k\) from \(W_k\) by removing \(v\) from the end and putting it at the start. We are now in the same situation described above, but with \(k\) increased to \(k+1\text{.}\) Since \(\Delta(G)\) is finite, this cannot go on forever and so, eventually, we obtain a proper colouring.
From Vizing’s Theorem, you may get the impression that the edge colouring problem for graphs is essentially solved as there are only two possibilities for the edge chromatic number: \(\Delta(G)\) or \(\Delta(G)+1\text{.}\) While, in some sense, this is true, one should not be fooled into thinking that computing the edge chromatic number is easy. In fact, it is NP-complete to determine whether a graph \(G\) has edge chromatic number equal to \(\Delta(G)\text{.}\) So, in this sense, computing the edge chromatic number is still quite hard.
Here is a YouTube video related to this section:
Here is a nice video by Tom Slama on Vizing’s Theorem.
