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

  • National Center for Women & Information Technology (NCWIT) has a learning package called Unplugged in a Box which has detailed lesson plan of this activity.
  • Computing Science Inside Workshop has an activity Graph Colouring which is a nice extension activity to this topic. This workshop aims to introduce pupils to the fundamental Computing Science notion of abstraction: the skill of drawing out the essence of a problem, solving it and then seeing what other problems can be solved using the same techniques. It introduces what seems to be a simple colouring problem for pupils to solve. Pupils will then try to draw out the rules and methods they used to solve the problem and apply them to a different and more realistic instance of the problem. The workshop will consider the importance of abstraction and automating reasoning to aid problem solving in Computing Science.
    Note: You will need to apply and register in order to receive the Workshop Pack for this activity.
  • Wikipedia: Graph Coloring
  • Wikipedia: Graph Theory
  • Wikipedia: Glossary of Graph Theory
  • Wapedia has a collection of information on Matching (Graph Theory) : In the mathematical discipline of graph theory, a matching or independent edge set in a graph is a set of edges without common vertices. It may also be an entire graph consisting of edges without common vertices.
  • The Mathmaniacs website has a similar activity (lesson 15).
  • The Discrete Mathematics Project, University of Colorado at Boulder has a complete set of Graph Theory Activities you can choose from.
  • Chris Caldwell, University of Tennessee has a great set of tutorials for learning Graph Theory and Colouring at Graph Theory Tutorials. Please note that you will need to register and instantly get access to the tutorials and exercises.
  • Flash & Math has Graph Theory Applets. Even though an advanced resource, these applets provide practice with some of the basic definitions of graph theory. In each case, a first page reminds the user of the definitions and notation involved in the concept, and then the applet chooses a handful of problems at random for the student to try.
  • nrich Maths has the following activities with notes and solutions provided:
  • Some Other Intractable Problems:Graph colouring is just one of thousands of intractable problems, many of which have confounded scientists for decades. Here are a couple more examples:
    • Travelling Salesperson Problem – Given a collection of cities connected by roads of different lengths, find the shortest possible path allowing for a ‘travelling salesperson’ to visit each city, before returning to their starting point. This may seem like a simple task, but the number of possible routes increases surprisingly quickly, leading to huge numbers with a relatively small amount of cities. Computer scientists have been pondering solutions to the TSP for over 50 years. In fact, there’s still a $1,000,000 prize up for grabs for an effective solution. Georgia Tech has a number of available TSP resources, including games and real-life examples.
    • Chess – Calculating a solution to a game of chess is not an intractable problem itself. In fact, computers have been beating humans at chess for over a decade. However, trying to calculate all of the possible paths to a solution leads to a combinatorial explosion, and demonstrates the limits of computer processing. A few other popular games that present intractable problems are Battleship, Minesweeper, and Sudoku.

Curriculum Links

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