Network colouring is an fascinating branch of mathematics, originally motivated by the four colour map theorem (first conjectured in 1852, but proved only in 1976). Network colouring has applications to register allocation in computers.

For each network there is a chromatic polynomial which gives the number of ways in which the network can be coloured with *x* colours (subject to the restriction that directly linked nodes have different colours). For example, this linear network can be coloured in two ways using *x* = 2 colours:

The corresponding chromatic polynomial is *x* (*x* − 1)^{3}, which is plotted below. Zeros at *x* = 0 and *x* = 1 indicate that at least 2 colours are required.

For the Petersen network below, the chromatic polynomial is:

*x* (*x* − 1) (*x* − 2) (*x*^{7} − 12 *x*^{6} + 67 *x*^{5} − 230 *x*^{4} + 529 *x*^{3} − 814 *x*^{2} + 775 *x* − 352)

This polynomial has zeros at 0, 1, 2, and 2.2051, and is plotted below:

Chromatic polynomials provide an interesting link between elementary and advanced mathematics, as well as an interesting case study of network algorithms.

See http://mathworld.wolfram.com/ChromaticPolynomial.html and http://www.sciencedirect.com/science/article/pii/S0021980068800870 for more info.