The Computational Complexity of the Tutte Plane: the Bipartite Case

1992/06/01 by Dirk Vertigan, Dominic Welsh · 3 citations
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Advanced Graph Theory Research #Bipartite graph #Chromatic polynomial #Combinatorics #Computer science #Discrete mathematics #Graph #Ising model #Markov Chains and Monte Carlo Methods #Mathematics #Partition (number theory) #Partition function (quantum field theory) #Physics #Planar #Planar graph #Potts model #Spanning tree #Statistical physics #Tutte polynomial #Voltage graph

paper · doi:10.1017/s0963548300000195

openalex publication_date 1992/06/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/22

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.

Citations

• Hard Enumeration Problems in Geometry and Combinatorics
• The Computational Complexity of Tutte Invariants for Planar Graphs
• On the computational complexity of the Jones and Tutte polynomials
• The Complexity of Enumeration and Reliability Problems

Cited by

• A Randomised Approximation Algorithm for Counting the Number of Forests in Dense Graphs
• Graph Polynomials and Their Applications I: The Tutte Polynomial
• Tutte polynomial [wikipedia]