Chapter 8 - Edge colourings

Summary

Edge colourings and timetables

An edge colouring of a graph G with the colours α₁, …, α_t is an assignment of the colours to the edges of G, one colour to each edge. Such a colouring is called proper if no pair of adjacent edges receive the same colour. More formally, an edge colouring of G with colours from the set C = {α₁, …, α_t} is a mapping f : E(G) → C. If f(e) = α_k then we say that the edge e is coloured α_k. The set of edges of colour α_k we denote by M(f, α_k). Then M(f, α_k) is a matching for every k = 1, …, t if and only if f is a proper edge colouring. Usually we shall think of C = {1, 2, …, t}. We shall call an edge colouring with these colours 1, …, t simply a t-colouring and call a path P (k, l)-coloured if its edges are alternately coloured with the colours k and l. A (k, l)-coloured path P is called maximal if there is no other (k, l)-coloured path P′ with V(P) ⊆ V(P′).

Of course, if we have too few colours in the set C then there is no valid proper edge colouring. We call the minimum t for which there exists a proper t-colouring of G the chromatic index of G, which we denote by X′(G).