Graph Colouring

Coloring a map (which is equivalent to a graph) sounds like a simple task, but in computer science this problem epitomizes a major area of research looking for solutions to problems that are easy to make up, but seem to require an intractable amount of time to solve.

This activity introduces graph colouring, and leads on to many variations and extensions that reach the cutting edge of computer science.

World Map

Activity description (PDF)

Related Resources

Curriculum Links

Great Principles of Computer Science [info]
  • Computation
New Zealand Curriculum [info]
Expand
  • Mathematics Level 2: Position and orientation