GraphLab › Graph colouring
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.
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.
Step through the example graph to see which colour each vertex gets and why. Add edges to make the graph harder to colour.