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.