Description

Graph colouring refers to a rather broad area of graph theory (here, graph meaning the discrete object with vertices and edges) concerned with questions arising from the assignment of labels (aka "colours") to particular elements of a graph, typically with certain constraints on the assignment. For example, consider a "vertex colouring" using (at most) k colours, which can be thought of as a function from the set of vertices of the graph to the integers from 1 to k. A fundamental question in graph colouring asks whether it is possible to find such a colouring for a fixed graph with the additional property that the colours assigned to neighbouring vertices are always distinct (if so, the graph is said to be k-colourable).

The area of graph colouring has many interesting and famous problems (both solved and unsolved ones!) and also enjoys practical applications from scheduling and timetabling, to bandwidth allocation and frequency assignment problems, as well as even solving Sudoku puzzles! This project gives the opportunity to study any and/or all of these and much more besides.

A natural starting point could be the famous four colour theorem, first posed/conjectured in 1852, and only finally solved (with the help of computers) in 1976. In common language, the result says that four colours suffice to colour any map so that countries with a common border are coloured with different colours. (In a more mathematical language, the theorem states that all planar graphs are 4-colourable.)

But there is a wide range of directions to look in, including but not limited to:

• ideas and techniques used in attempted proofs (both successful and unsuccessful): Kempe chains, reduction, discharging;
• related results: Grötzsch's Theorem (triangle-free planar graphs are 3-colourable), the empire problem, the Earth-Moon problem, colouring maps on other surfaces (with holes);
• computer assisted proofs;
• algorithmic questions, finding efficient colouring algorithms;
• other types of colouring: list colouring, fractional colouring, L(2,1)-colouring, edge colouring, total colouring (colouring both vertices and edges simultaneously);
• Ramsey theory (finding ordered substructures in arbitrary colourings);
• The Hadwiger–Nelson conjecture, concerning the chromatic number of a particular family of geometric graphs, and related colouring problems;
• properties of the chromatic polynomial and related algebraic graph theory;
• colouring of random graphs and their properties.

Essential prior/companion modules

Discrete Mathematics is essential. (You do not need to have taken the graph colouring topic in the seminars in the second term.)

Some basic geometric topology (Euler characteristic, genus) might be helpful for the generalisations to surfaces with holes; and some familiarity with probability would be helpful if you are interesting in studying random graphs.

Resources

A good starting point is the book Graphs, Colourings and the Four-colour Theorem, R. Wilson, 2002.

You can also search online for "graph colouring" or some of the phrases above for more information.

If you need a reminder of some of the graph-theoretic concepts from Discrete Mathematics have a look at Modern Graph Theory, B. Bollobás, 1998, or Graph Theory, R. Diestel, 2016, free preview version available online.

Get in touch if you have any questions!

email: Nicholas Georgiou