by Mike Fellows and Frances Rosamond

Colouring a graph properly (no adjacent vertices can receive the same colour) is important in scheduling (classrooms, jobs, exams, resources). The vertices represent the jobs. An edge between two vertices indicates a conflict.  Colours are the timeslots. Two jobs cannot be assigned the same timeslot or else they will be in conflict (both rely on a shared resource, for example).

Colouring a graph leads us to a Rainbow Serpent story. The snake has colourful stripes like a rainbow. Like a rainbow,  no two colours are repeated (i.e., no two adjacent stripes have the same colour).  Rainbow Serpent likes to be present and observe everything, but remain hidden. Sometimes the Rainbow Serpent will surface to talk to the people and teach them. The vertices on the graph represent places where the snake might be. If two adjacent vertices are coloured the same, then we know the snake is not there. In order to see Rainbow Serpent, colours must not be repeated.  Continue reading Rainbow Serpent: Connecting Mathematics and Aboriginal Culture →