On Some Randomised Algorithms for Graph Colouring

The paper investigates the application of the Mean Field Annealing (MFA) approach to graph colouring using the Petford and Welsh algorithm as a Generalised Boltzmann Machine. The operation of the MFA algorithm for a Generalised Boltzmann Machine is characterised by the de nition of an appropriate energy function which the algorithm attempts to minimise. In the case of graph colouring a relationship between the critical temperature of the MFA algorithm and the minimal eigenvalue of the graph to be coloured is demonstrated. In other words, we show how the structure of the solution space (existence of some global/local minima of the adapted energy function) depends on the parameter called temperature. Some experimental results are presented including comparison with a Multi State Bitstream Neural Network.