Graph colouring is a theoretical problem within Graph Theory, where we seek to assign colours to the vertices of a graph so that no two vertices of the same colour are connected by an edge. Since colouring every vertex a different colour will easily achieve this, we are often interested in minimising the number of colours required. Colouring has many applications to scheduling problems for example the task of scheduling university examinations for thousands of students. Such a problem can be modeled by a graph in which there is a vertex for each exam, and two `exams' are connected by an edge precisely when there is a student that must sit both of them. A colouring of this graph then corresponds to a timetabling of the situation where no student must be in two places at once.
References A Touch of Color: Graph Coloring.
 Frank Thomson Leighton. A graph coloring algorithm for large scheduling problems. JOURNAL OF RESEARCH of the National Bureau of Standards, 1979
Optagelsesbegrænsning: maks. 3 grupper