A very simple algorithm for estimating the number of k-colourings of a low-degree graph.

[an error occurred while processing this directive] An error occured whilst processing this directive

A very simple algorithm for estimating the number of k-colourings of a low-degree graph.

Mark Jerrum

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 An error occured whilst processing this directive