GraphLab

Graph theory & algorithm visualizer
About Graph colouring

GraphLab › Graph colouring

Graph Coloring Visualizer: Greedy Vertex Colouring Step by Step

Graph colouring (graph coloring) gives each vertex a colour so that no two vertices joined by an edge have the same colour. The smallest number of colours that works is the chromatic number of the graph. Colouring is used for timetables, exam scheduling, map colouring and register allocation.

How the greedy algorithm works

  1. Go through the vertices one by one.
  2. Give each vertex the smallest colour number that none of its already coloured neighbours uses.

The greedy method is fast and always gives a valid colouring. It may use more colours than the chromatic number, depending on the order of the vertices.

Try it in GraphLab

Step through the example graph to see which colour each vertex gets and why. Add edges to make the graph harder to colour.

More topics