Combinatorics, Probability and Computing

Research Article

The Computational Complexity of the Tutte Plane: the Bipartite Case

D. L. Vertigana1 and D. J. A. Welsha2

a1 Mathematical Institute, University of Oxford, 24–29 St Giles, Oxford OX1 3LB

a2 Merton College, University of Oxford, Oxford OX1 4JD and University of Bonn

Abstract

Along different curves and at different points of the (x, y)-plane the Tutte polynomial evaluates a wide range of quantities. Some of these, such as the number of spanning trees of a graph and the partition function of the planar Ising model, can be computed in polynomial time, others are # P-hard. Here we give a complete characterisation of which points and curves are easy/hard in the bipartite case.

(Received October 15 1991)