Abstract: A fully polynomial randomised approximation scheme is presented for estimating the number of (vertex) k-colourings of a graph of maximum degree Delta, when k >= Delta + 1.
Keywords: Analysis of algorithms, Antiferromagnetic Potts model, Randomised approximation scheme, Rapidly mixing Markov chains, Vertex colouring of graphs.
LFCS report ECS-LFCS-94-290, April 1994.
Previous | Index | Next