Graph Polynomials and Their Applications I: The Tutte Polynomial

In this survey of graph polynomials, we emphasize the Tutte polynomial and a selection of closely related graph polynomials. We explore some of the Tutte polynomial's many properties and applications and we use the Tutte polynomial to showcase a variety of principles and techniques for graph polynomials in general. These include several ways in which a graph polynomial may be defined and methods for extracting combinatorial information and algebraic properties from a graph polynomial. We also use the Tutte polynomial to demonstrate how graph polynomials may be both specialized and generalized, and how they can encode information relevant to physical applications. We conclude with a brief discussion of computational complexity considerations.

• Publication year

  2008

• Venue

  Structural Analysis of Complex Networks

• Publication date

  2008-03-20

• Fields of study

  Mathematics, Physics, Computer Science

• Identifiers
  DOI 10.1007/978-0-8176-4789-6_9arXiv 0803.3079
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Modern Graph Theory

  2013influential reference
• The Tutte polynomial of a morphism of matroids - 5. Derivatives as generating functions of Tutte activities

  2012cited by this paper
• The Tutte Polynomial Part I: General Theory

  2010cited by this paper
• Graph Minors

  2009cited by this paper
• Bounds for the coefficients of flow polynomials

  2007cited by this paper
• Enumerating degree sequences in digraphs and a cycle-cocycle reversing system

  2007influential reference
• Graphs with Chromatic Roots in the Interval (1, 2)

  2007cited by this paper
• COMPLEXITY OF GRAPH POLYNOMIALS

  2007cited by this paper
• TUTTE-WHITNEY POLYNOMIALS: SOME HISTORY AND GENERALIZATIONS

  2007cited by this paper
• Regions Without Complex Zeros for Chromatic Polynomials on Graphs with Bounded Degree

  2007cited by this paper
• On the evaluation at (j, j2) of the Tutte polynomial of a ternary matroid

  2007cited by this paper
• The Complexity of Counting Colourings of Subgraphs of the Grid

  2006cited by this paper
• Computing Graph Polynomials on Graphs of Bounded Clique-Width

  2006cited by this paper
• Inapproximability of the Tutte polynomial

  2006cited by this paper
• Approximating clique-width and branch-width

  2006cited by this paper
• On the colored Tutte polynomial of a graph of bounded treewidth

  2006cited by this paper
• Zero-Free Intervals for Flow Polynomials of Near-Cubic Graphs

  2006cited by this paper
• Absence of Zeros for the Chromatic Polynomial on Bounded Degree Graphs

  2006cited by this paper
• Activity preserving bijections between spanning trees and orientations in graphs

  2005cited by this paper
• Planar Triangulations with Real Chromatic Roots Arbitrarily Close to 4

  2005cited by this paper
• Chromatic polynomials and chro-maticity of graphs

  2005cited by this paper
• Special issue on the Tutte polynomial

  2004cited by this paper
• Graph-polynomials

  2004cited by this paper
• Exploring the Tutte-Martin connection

  2004cited by this paper
• Identities for circuit partition polynomials, with applications to the Tutte polynomial

  2004influential reference
• The largest non-integer real zero of chromatic polynomials of graphs with fixed order

  2004cited by this paper
• On upper bounds for real roots of chromatic polynomials

  2004cited by this paper
• Exact Potts Model Partition Functions for Strips of the Triangular Lattice

  2002cited by this paper
• Zeros of chromatic and flow polynomials of graphs

  2002cited by this paper
• Homogeneous multivariate polynomials with the half-plane property

  2002cited by this paper
• Potts Model on Infinite Graphs and the Limit of Chromatic Polynomials

  2002cited by this paper
• Colored Tutte polynomials and Kaufman brackets for graphs of bounded tree width

  2001cited by this paper
• Algebraic Graph Theory

  2001cited by this paper
• The Chip Firing Game and Matroid Complexes

  2001cited by this paper
• Proofs from THE BOOK

  2001cited by this paper
• CORR 2001-24 The Largest non-integer Zero of Chromatic Polynomials of Graphs with Fixed Order

  2001cited by this paper
• Irreducibility of the Tutte Polynomial of a Connected Matroid

  2001cited by this paper
• Orientations Acycliques et le Polyno^me Chromatique

  2001cited by this paper
• The Potts model and the Tutte polynomial

  2000cited by this paper
• Exact Potts model partition functions on wider arbitrary-length strips of the square lattice

  2000cited by this paper
• Chromatic Roots are Dense in the Whole Complex Plane

  2000cited by this paper
• Series and parallel reductions for the Tutte polynomial

  2000cited by this paper
• On the Chromatic Roots of Generalized Theta Graphs

  2000cited by this paper
• A Personal List of Unsolved Problems Concerning Lattice Gases and Antiferromagnetic Potts Models

  2000cited by this paper
• Bounds on the Complex Zeros of (Di)Chromatic Polynomials and Potts-Model Partition Functions

  1999cited by this paper
• Chip-Firing and the Critical Group of a Graph

  1999cited by this paper
• The Tutte polynomial

  1999cited by this paper
• Chromatic polynomials and their zeros and asymptotic limits for families of graphs

  1999influential reference
• Enumerative Combinatorics: Index

  1999cited by this paper
• An algorithm for the Tutte polynomials of graphs of bounded treewidth

  1998cited by this paper
• External and internal elements of a matroid basis

  1998cited by this paper
• Ground-state degeneracy of Potts antiferromagnets: cases with noncompact W boundaries having multiple points at

  1998cited by this paper
• Reliability Polynomials: A Survey

  1998cited by this paper
• Ground state entropy of Potts antiferromagnets on homeomorphic families of strip graphs

  1998cited by this paper
• Evaluating the Tutte Polynomial for Graphs of Bounded Tree-Width

  1998cited by this paper
• Bicycle Dimension and Special Points of the Tutte Polynomial

  1998cited by this paper
• Proofs from THE BOOK

  1998cited by this paper
• A bibliography on chromatic polynomials

  1997influential reference
• A Convolution Formula for the Tutte Polynomial

  1997cited by this paper
• Families of Graphs with W_r({G},q) Functions That Are Nonanalytic at 1/q=0

  1997cited by this paper
• Chip firing and the tutte polynomial

  1997cited by this paper
• The Zero-Free Intervals for Chromatic Polynomials of Graphs

  1997cited by this paper
• Integer Flows and Cycle Covers of Graphs

  1997cited by this paper
• Graph Minors: XV. Giant Steps

  1996cited by this paper
• Asymptotic limits and zeros of chromatic polynomials and ground-state entropy of Potts antiferromagnets

  1996cited by this paper
• Polynomial Time Randomized Approximation Schemes for Tutte-Gröthendieck Invariants: The Dense Case

  1995cited by this paper
• Computing the Tutte Polynomial of a Graph of Moderate Size

  1995cited by this paper
• A Tourist Guide through Treewidth

  1993cited by this paper
• Abelian avalanches and Tutte polynomials

  1993cited by this paper
• The Coefficients of the Tutte Polynomial Are Not Unimodal

  1993cited by this paper
• A Zero-Free Interval for Chromatic Polynomials of Graphs

  1993cited by this paper
• Abelian Avalanches and Tutte Polynomials

  1992cited by this paper
• A zero-free interval for chromatic polynomials

  1992cited by this paper
• Matroid Applications: The Tutte Polynomial and Its Applications

  1992influential reference
• The Computational Complexity of the Tutte Plane: the Bipartite Case

  1992cited by this paper
• Matroid Applications: Homology and Shellability of Matroids and Geometric Lattices

  1992influential reference
• On the computational complexity of the Jones and Tutte polynomials

  1990cited by this paper
• Polynomial-Time Approximation Algorithms for the Ising Model

  1990cited by this paper
• On graph invariants given by linear recurrence relations

  1990cited by this paper
• Self-organized critical state of sandpile automaton models.

  1990cited by this paper
• Self-organized criticality.

  1988cited by this paper
• On the evaluation at (3, 3) of the Tutte polynomial of a graph

  1988cited by this paper
• Combinatorial Geometries: The Möbius Function and the Characteristic Polynomial

  1987cited by this paper
• A spanning tree expansion of the jones polynomial

  1987cited by this paper
• Two-dimensional monomer-dimer systems are computationally intractable

  1987cited by this paper
• Graph Minors. II. Algorithmic Aspects of Tree-Width

  1986cited by this paper
• Graph minors. III. Planar tree-width

  1984cited by this paper
• An evaluation of

  1983cited by this paper
• ON THE INTERPRETATION OF WHITNEY NUMBERS THROUGH ARRANGEMENTS OF HYPERPLANES, ZONOTOPES, NON-RADON PARTITIONS, AND ORIENTATIONS OF GRAPHS

  1983influential reference
• private communication

  1983cited by this paper
• Graph minors. I. Excluding a forest

  1983cited by this paper
• Combinatorics and commutative algebra

  1983cited by this paper
• The NP-Completeness Column: An Ongoing Guide

  1982cited by this paper
• On Crapo's Beta Invariant for Matroids

  1982cited by this paper
• Forests and score vectors

  1981cited by this paper
• Nowhere-zero 6-flows

  1981cited by this paper
• Decompositions of Rational Convex Polytopes

  1980cited by this paper
• Decompositions of Simplicial Complexes Related to Diameters of Convex Polyhedra

  1980influential reference
• Johnson: computers and intractability: a guide to the theory of np- completeness (freeman

  1979cited by this paper
• Graph theory and related topics

  1979cited by this paper

• Tutte polynomials of single interior pericondensed hexagonal systems

  2026cites this paper
• Around the Merino--Welsh conjecture: improving Jackson's inequality

  2025cites this paper
• Counting with two-level polynomials

  2025cites this paper
• Newly generated path graph matching-polynomial matrix of integration to solve initial-value, finite-value and infinite-boundary-value problems

  2025cites this paper
• Coloring Geometric Hypergraphs: A Survey

  2025cites this paper
• Distinguishing and Reconstructing Directed Graphs by their B\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\pmb {B}$$

  2024cites this paper
• The extra basis in noncommuting variables

  2024cites this paper
• The Tutte Polynomials of a Class of Flower Graph f(Cm,Fn)

  2024cites this paper
• The Merino–Welsh conjecture is false for matroids

  2024cites this paper
• Kramers–Wannier duality and Tutte polynomials

  2024cites this paper
• Tutte polynomial of self-similar network models with applications

  2023cites this paper
• On maximum graphs in Tutte polynomial posets

  2023influential citation
• Graph polynomials associated with Dyson-Schwinger equations

  2023influential citation
• Permutation Tutte polynomial

  2023cites this paper
• The Merino--Welsh conjecture is false for matroids

  2023cites this paper
• Short proof of a theorem of Brylawski on the coefficients of the Tutte polynomial

  2023cites this paper
• The Complexity of the Greedoid Tutte Polynomial

  2023cites this paper
• Proper q-caterpillars are distinguished by their Chromatic Symmetric Functions

  2023cites this paper
• A Chip-Firing Game for Biocrust Reverse Succession

  2023cites this paper
• Second leap hyper-Zagreb coindex of certain benzenoid structures and their polymomials

  2023cites this paper
• Little tricks leading to a significant acceleration of the calculation of the reliability of a random graph

  2023cites this paper
• Measures of spin ordering in the Potts model with a generalized external magnetic field

  2023cites this paper
• Learning-Based Approaches for Graph Problems: A Survey

  2022cites this paper
• Interpretations for the Tutte polynomials of morphisms of matroids

  2022cites this paper
• Deletion-contraction and the surface Tutte polynomial

  2022cites this paper
• ALGEBRAIC COMBINATORICS

  2022cites this paper
• Extremal graphs for the Tutte polynomial

  2022influential citation
• Short proof of a theorem of Brylawski on the coefficients of the Tutte polynomial

  2022cites this paper
• Beyond Windability: An FPRAS for The Six-Vertex Model

  2022cites this paper
• Irreducibility of the Tutte polynomial of an embedded graph

  2022cites this paper
• Criterion for a graph to admit a good orientation in terms of leaf blocks

  2022cites this paper
• Tutte polynomials of vertex-weighted graphs and group cohomology

  2021cites this paper
• Evaluations of Tutte polynomials of regular graphs

  2021cites this paper
• Functional Relations on Anisotropic Potts Models: from Biggs Formula to the Tetrahedron Equation

  2021cites this paper
• On the Roots of the Modified Orbit Polynomial of a Graph

  2021cites this paper
• Tutte polynomials of vertex-weighted graphs and group cohomology

  2021cites this paper
• Upper bound for the number of spanning forests of regular graphs

  2021cites this paper
• Network Analyzing by the Aid of Orbit Polynomial

  2021cites this paper
• Orbit Polynomial of Graphs versus Polynomial with Integer Coefficients

  2021cites this paper
• On the zeros of the partial Hosoya polynomial of graphs

  2020cites this paper
• Simulation of all-terminal reliability of an undirected network using the reliability polynomial

  2020cites this paper
• On the Rank Functions of Powerful Sets

  2020cites this paper
• On the activities and partitions of the vertex subsets of graphs

  2020cites this paper
• A Vertex-Weighted Tutte Symmetric Function, and Constructing Graphs with Equal Chromatic Symmetric Function

  2020cites this paper
• Relations and bounds for the zeros of graph polynomials using vertex orbits

  2020cites this paper
• Multivariate polynomial graph invariants: dualities and critical properties

  2020influential citation
• Universal Tutte polynomial

  2020cites this paper
• Some New Ideas About Obtaining and Estimating Reliability Polynomial of a Random Graph

  2020cites this paper
• Interpretations of the Tutte and characteristic polynomials of matroids

  2019cites this paper
• Interpretations of the Tutte and characteristic polynomials of matroids

  2019cites this paper
• Towards detecting structural branching and cyclicity in graphs: A polynomial-based approach

  2019cites this paper
• Fast Rough Bounds for the Coefficients of the Network Reliability Polynomial

  2019cites this paper
• Tutte Polynomials of Two Self-similar Network Models

  2019cites this paper
• The behavior of Tutte polynomials of graphs under five graph operations and its applications

  2019cites this paper
• Tutte short exact sequences of graphs

  2019cites this paper
• Tutte-Whitney Polynomials for Directed Graphs and Maps

  2019cites this paper
• Formulas counting spanning trees in line graphs and their extensions

  2019cites this paper
• Tutte Polynomials of Two Self-similar Network Models

  2018cites this paper
• Asymptotic behavior of acyclic and cyclic orientations of directed lattice graphs

  2018cites this paper
• The zero forcing polynomial of a graph

  2018cites this paper
• Locally free representations of quivers over commutative Frobenius algebras

  2018cites this paper
• Graph measures with high discrimination power revisited: A random polynomial approach

  2018cites this paper
• Networks, (K)nots, Nucleotides, and Nanostructures

  2018cites this paper
• The complexity of greedoid Tutte polynomials

  2018cites this paper
• Tutte Polynomial of Generalized Flower Graphs

  2017cites this paper
• Several Extreme Coefficients of the Tutte Polynomial of Graphs

  2017cites this paper
• Approximability of the Six-vertex Model

  2017cites this paper
• The Expansion of a Chord Diagram and the Tutte Polynomial

  2017cites this paper
• A logician's view of graph polynomials

  2017cites this paper
• Counting Markov equivalence classes for DAG models on trees

  2017cites this paper
• Derivatives and real roots of graph polynomials

  2016cites this paper
• Practical Notes on Obtaining Reliability Polynomials

  2016cites this paper
• Order quasisymmetric functions distinguish rooted trees

  2016cites this paper
• A Tutte Polynomial for Maps

  2016cites this paper
• Tutte polynomials for benzenoid systems with one branched hexagon

  2016cites this paper
• The Interlace Polynomial

  2016cites this paper
• A forest building process on simple graphs

  2016cites this paper
• The Tutte and the Jones Polynomials

  2016influential citation
• Jernej Azarija Some Results From Algebraic Graph Theory

  2016cites this paper
• Properties of chromatic polynomials of hypergraphs not held for chromatic polynomials of graphs

  2016cites this paper
• Counting Markov Equivalence Classes by Number of Immoralities

  2016cites this paper
• Semantic Equivalence of Graph Polynomials Definable in Second Order Logic

  2016cites this paper
• Tutte polynomial of some multigraphs

  2015cites this paper
• Defect polynomials and Tutte polynomials of some asymmetric graphs

  2015cites this paper
• Chromatic and flow polynomials of generalized vertex join graphs and outerplanar graphs

  2015cites this paper
• Efficient Computation of Chromatic and Flow Polynomials

  2015cites this paper
• Discrimination power of graph measures based on complex zeros of the partial Hosoya polynomial

  2015cites this paper
• Encoding structural information uniquely with polynomial-based descriptors by employing the Randić matrix

  2015cites this paper
• Discrimination Power of Polynomial-Based Descriptors for Graphs by Using Functional Matrices

  2015cites this paper
• Counterexamples to a conjecture of Balasubramanian and Parthasarathy

  2015cites this paper
• SOME POLYNOMIAL INVARIANTS OF A FAMILY OF GRAPHS

  2015cites this paper
• Tutte polynomial of a fractal scale-free lattice

  2014influential citation
• Graph Polynomials Motivated by Gene Rearrangements in Ciliates

  2014cites this paper
• The Tutte polynomial and related polynomials

  2014cites this paper
• Spectral Theory for Dynamics on Graphs Containing Attractive and Repulsive Interactions

  2014cites this paper
• Subset Glauber Dynamics on Graphs, Hypergraphs and Matroids of Bounded Tree-Width

  2014cites this paper
• The Algebra of Gene Assembly in Ciliates

  2014cites this paper
• A general notion of activity for the Tutte polynomial

  2014cites this paper
• Matroids, delta-matroids and embedded graphs

  2014cites this paper
• Algebraic and Geometric Methods in Enumerative Combinatorics

  2014cites this paper