10.1.1. Approximation algorithms

The Greedy Algorithm

  • Order the vertices of the given graph G in any order.
  • Colour by the colour 1,
  • Colour by 1 if and by 2 otherwise.
  • We colour each vertex the by the smallest colour it can have at the stage.

The problem: this colouring may and usually does use many more colours than necessary.

However, it is also true that for every graph the vertices can be ordered in such a way that the greedy algorithm uses as few colours as possible.