Chromatic polynomials

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) (x7 − 12 x6 + 67 x5 − 230 x4 + 529 x3 − 814 x2 + 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.


Advertisements

One thought on “Chromatic polynomials

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s