# 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.

### Related post:

- Reisch receives SUNY Chancellor’s Award | News, Sports, Jobs – Evening Observer
- An overall 2nd place for Malta in an International Mental Mathematics Challenge – Malta Independent Online
- DU Admissions 2019: Mathematics Must In Best Of Four Subjects For Admission Into Eco(H); JMC, Stephen’s Stick To Old Rule – Swarajya
- Agami Education Foundation holds teachers’ training on Teaching Mathematics by Olympiad Technique – Dhaka Tribune
- 2nd place for Malta in international Mental Mathematics Challenge – Newsbook
- Darlington pupils among most-skilled mathematics in the UK – Darlington and Stockton Times
- Women and minority faculty in science, technology, engineering and mathematics (STEM) – Open Access Government
- The messy mathematics of British Columbia’s CleanBC plan – Business in Vancouver
- All Limerick student’s hard work adds up to him winning top mathematics award in Ireland – Limerick Leader
- CMU-Q researchers explore the mathematics of personalised medicine – The Peninsula Qatar