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.

Other Resources

• Wikipedia: Graph Coloring
• The Mathmaniacs web site has a similar activity (lesson 15).

Curriculum Links

Graph colouring is a great problem-solving activity for a mathematics course.

New Zealand Curriculum Achievement Objectives

• Mathematics Level 2: Position and orientation
  • Describe different views and pathways from locations on a map.

ACM K12 Model Curriculum

• Level I (Grades 6-8) Topic 11: Understand the graph as a tool for representing problem states and solutions to complex problems.

Great Principles of Computer Science

• Computation