Online Graph Colouring

This paper considers the problem of online graph colouring. An algorithm for vertex-colouring graphs is said to be online if each vertex is irrevocably assigned a colour before later vertices are considered. We first introduce the problem formally and define a perfomance metric to evaluate the success of an online colouring algorithm. Then, several upper and lower bounds are presented on the performance ratio for any algorithm solving the online graph colouring problem. These general bounds are shown to hold even when we relax and vary the conditions of the problem. Next, specific algorithms are presented and analyzed on how they perform in specific cases as well as in the general case. Finally, a discussion of future directions for research is presented