Graph colouring by maximal evidence edge adding

A colouring of a graph G=(N; E) is any mapping c: N! C, where C is the set ofcolours', for convenience usually a subset of the natural numbers. Unless otherwise stated we will assume that N= f1;:::; ng. We say that a colouring c is proper, if there is no pair u; v 2 N of adjacent vertices of the same colour (c (u)= c (v)). A graph G is k {colourable, if there is a proper colouring with card (C) k colours. The minimal k for which there is a proper k {colouring is the chromatic number G, denoted (G). The decision problem of k {colouring is: INPUT: graph G, integer k QUESTION: is G k {colourable? The problem is NP {hard for general graphs 10], but also for many special classes of graphs including planar graphs 9], regular graphs 18], etc.. It therefore seems unlikely that it will be possible to nd a fast (ie polynomial-time) algorithm to solve these problems. It is also unlikely that there is a polynomial approximation algorithm; if there is a polynomial algorithm which nds a 2 (G)-colouring of G, then there is a polynomial algorithm which nds the exact colouring 8].