ACiD
Algorithms and Complexity in Durham
A research group in the Department of Computer Science

The Heawood Graph is named after the mathematician Percy John Heawood (1861-1955), who worked for many years at Durham University. He is famous for his results on graph colouring. In 1890 he published a paper in which he pointed out an error in Kempe's approach to prove the Four-Colour Conjecture for planar graphs. In the same paper he used Kempe's approach to prove the Five-Colour Theorem for planar graphs, and he proved an upper bound for the chromatic number of graphs embeddable on a surface of genus at least one. As well as being a well-regarded member of the university community, Heawood was a respected resident of Durham City. He raised the money necessary to ensure that the foundations of Durham Castle were permanently secured; without him the castle would not be standing today.