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
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)