I went to a mathematics talk last week (Weds 7 Jan) where Adam van Tuyl talked in passing about graph colouring, which is the same topic I mentioned (very briefly!) during the first class.
- you can read about the general concept of graph colouring on Wikipedia; the basic idea is to take some graph and assign colours to its nodes, or vertices, in such a way that no two nodes that are connected by an edge have the same colour.
- the chromatic number is defined as the number of distinct colours needed
- four-colour theorem specifically applies to graphs that can be generated by translating partitions of the plane into neighbour graphs (i.e. each region is a vertex, each edge represents a pair of neighbours). These are easier than general graphs: you can easily see that a complete graph (i.e. a graph where every pair of nodes is connected by an edge) with \(k\) nodes also has a chromatic number equal to \(k\) (i.e. every node must have its own colour).
- there are applications (among others) in scheduling (this was brought up by the speaker, and is also discussed on the Wikipedia page). If nodes are courses we need to schedule and edges represent pairs of courses that have at least one student in common (so that those two courses can’t be scheduled at the same time), then you need a number of time slots equal to the chromatic number in order to allow everyone to fill their schedules without conflicts (unless you have better technology)
- the speaker discussed mathematics, with an associated algorithm, that would allow you to compute the chromatic number without actually figuring out the colouring
- graph colouring is a notoriously hard comptuational problem (again see the Wikipedia page). Some of the existing algorithms are implemented in Python as part of the Sagemath project)
- project ideas: what can we find out about some interesting graphs (e.g.co-authorship on MathSciNet or ArXiv? Can we ask students in the class to contribute data, e.g. something simple like who knows whom?) Graph coloring is a difficult problem, so doing it for big graphs might be tough (I don’t know what impractically big corresponds to – 100? 1000? 10,000?)