2010/09/01 by Gary Haggard, David J. Pearce, Gordon Royle · 1 citation
Mathematics · #Advanced Combinatorial Mathematics #Stochastic processes and statistical mechanics #Markov Chains and Monte Carlo Methods #Tutte polynomial #Chromatic polynomial #Potts model #Combinatorics #Mathematics #Discrete mathematics #Graph coloring #Bracket polynomial #Polynomial #Matrix polynomial #Graph #Voltage graph #Alternating polynomial #Line graph
paper · doi:10.1145/1824801.1824802
openalex publication_date 2010/09/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/15
The Tutte polynomial of a graph, also known as the partition function of the q -state Potts model is a 2-variable polynomial graph invariant of considerable importance in both combinatorics and statistical physics. It contains several other polynomial invariants, such as the chromatic polynomial and flow polynomial as partial evaluations, and various numerical invariants such as the number of spanning trees as complete evaluations. However despite its ubiquity, there are no widely available effective computational tools able to compute the Tutte polynomial of a general graph of reasonable size. In this article we describe the implementation of a program that exploits isomorphisms in the computation tree to extend the range of graphs for which it is feasible to compute their Tutte polynomials, and we demonstrate the utility of the program by finding counterexamples to a conjecture of Welsh on the location of the real flow roots of a graph.