Edge Colouring and Chromatic Indexes

We have already looked at Vertex Colouring and Chromatic Numbers, and now we are going to examine edge colouring and the analogous chromatic index.

Suppose that we wanted to colour the edges of a graph such that no vertex contains two edges of the same colour. Of course, we would have to look at graphs omitting loops as they would quickly violate our problem of edge colouring. For example, the following graph depicts an edge colour of $4$ different colours (red, orange, green, and blue):

Hence, we can say that if this graph is $G$, then $G$ is $4$-colourable in terms of edges. Once again, we are often interested in the smallest number of colours we can use to meet the condition above.

Definition: The Chromatic Index of a graph $G$ denoted $\chi ' (G)$ is the smallest integer $k$ such that $G$ is edge $k$-colourable (and thus $G$ has a good edge $k$-colouring).

For our example above, it turns out that $\chi ' (G) = 4$. How did we know this was the smallest number of colours we could use?

Recall that in vertex colouring we looked at potential upper and lower bounds for $\chi (G)$. We can do the exact same for edge colouring. Note that we have found a good edge $4$-colouring for our graph above. Hence we know that $\chi ' (G) ≤ 4$. However, we also note that the maximum degree in the graph, $\Delta (G) = 4$. Hence $4 ≤ \chi ' (G)$. Since $4 ≤ \chi ' (G) ≤ 4$, then clearly $\chi ' (G) = 4$.

Now let's look at some chromatic indexes for some common graphs.

Graph	Chromatic Index $\chi ' (G)$	Explanation
Even Cycle Graphs, $C_{2n}$	$\chi ' (C_{2n}) = 2$	All even cycle graphs have an even number of edges. We can take half of these edges and colour them $1$, and take the other half of the edges and colour them $2$. No vertex will have two edges of the same colour.
Odd Cycle Graphs, $C_{2n+1}$	$\chi ' (C_{2n + 1}) = 3$	You can alternate edge colours between two colours until you get to the last edge which will need a third colour always.
Path Graphs, $P_n$	$\chi ' (P_n) = 2$	You can alternate between $2$ edge colours.
Tree Graphs, $T$	$\chi ' (T) = \Delta (T)$	Trees are acyclic, so we don't need to worry about any edges wrapping around causing problems. We will need exactly $\Delta (T)$ colours for any vertices that have the maximum degree nevertheless.

We note that if we can find a good edge $k$-colouring of a graph $G$, we can use that as an upper bound for $\chi ' (G)$. Additionally, we know that the maximum degree in a graph can be used as a lower bound for the chromatic index.