1st Edition

Handbook of the Tutte Polynomial and Related Topics

Edited By Joanna A. Ellis-Monaghan, Iain Moffatt Copyright 2022
    804 Pages 164 B/W Illustrations
    by Chapman & Hall

    804 Pages 164 B/W Illustrations
    by Chapman & Hall

    The Tutte Polynomial touches on nearly every area of combinatorics as well as many other fields, including statistical mechanics, coding theory, and DNA sequencing. It is one of the most studied graph polynomials.

    Handbook of the Tutte Polynomial and Related Topics is the first handbook published on the Tutte Polynomial. It consists of thirty-four chapters written by experts in the field, which collectively offer a concise overview of the polynomial’s many properties and applications. Each chapter covers a different aspect of the Tutte polynomial and contains the central results and references for its topic. The chapters are organized into six parts. Part I describes the fundamental properties of the Tutte polynomial, providing an overview of the Tutte polynomial and the necessary background for the rest of the handbook. Part II is concerned with questions of computation, complexity, and approximation for the Tutte polynomial; Part III covers a selection of related graph polynomials; Part IV discusses a range of applications of the Tutte polynomial to mathematics, physics, and biology; Part V includes various extensions and generalizations of the Tutte polynomial; and Part VI provides a history of the development of the Tutte polynomial.


    • Written in an accessible style for non-experts, yet extensive enough for experts
    • Serves as a comprehensive and accessible introduction to the theory of graph polynomials for researchers in mathematics, physics, and computer science
    • Provides an extensive reference volume for the evaluations, theorems, and properties of the Tutte polynomial and related graph, matroid, and knot invariants
    • Offers broad coverage, touching on the wide range of applications of the Tutte polynomial and its various specializations

    I. Fundamentals.

    1. Graph theory.
    Joanna A. Ellis-Monaghan, Iain Moffatt

    2. The Tutte Polynomial for Graphs.
    Joanna A. Ellis-Monaghan Iain Moffatt

    3. Essential Properties of the Tutte Polynomial.
    Béla Bollobás, Oliver Riordan

    4. Matroid theory.
    James Oxley

    5. Tutte Polynomial Activities.
    Spencer Backman

    6. Tutte Uniqueness and Tutte Equivalence.
    Joseph E. Bonin, Anna de Mier

    II. Computation.

    7. Computational Techniques.
    Criel Merino

    8. Computational Resources.
    David Pearce, Gordon F. Royle

    9. The Exact Complexity of the Tutte Polynomial.
    Tomer Kotek, Johann A. Makowsky

    10. Approximating the Tutte Polynomial.
    Magnus Bordewich

    III. Specializations.

    11. Foundations of the Chromatic Polynomial.
    Fengming Dong, Khee Meng Koh

    12. Flows and Colorings.
    Delia Garijo, Andrew Goodall, Jaroslav Nešeťril

    13. Skein Polynomials and the Tutte Polynomial when x = y.
    Joanna A. Ellis-Monaghan, Iain Moffatt

    14. The Interlace Polynomial and the Tutte–Martin Polynomial.
    Robert Brijder, Hendrik Jan Hoogeboom

    IV. Applications.

    15. Network Reliability.
    Jason I. Brown, Charles J. Colbourn

    16. Codes.
    Thomas Britz, Peter J. Cameron

    17. The Chip-Firing Game and the Sandpile Model.
    Criel Merino

    18. The Tutte Polynomial and Knot Theory.
    Stephen Huggett

    19. Quantum Field Theory Connections.
    Adrian Tanasa

    20. The Potts and Random-Cluster Models.
    Geoffrey Grimmett

    21. Where Tutte and Holant meet: a view from Counting Complexity.
    Jin-Yi Cai, Tyson Williams

    22. Polynomials and Graph Homomorphisms.
    Delia Garijo, Andrew Goodall, Jaroslav Nešeťril, Guus Regts

    V. Extensions.

    23. Digraph Analogues of the Tutte Polynomial.
    Timothy Y. Chow

    24. Multivariable, Parameterized, and Colored Extensions of the Tutte Polynomial.
    Lorenzo Traldi

    25. Zeros of the Tutte Polynomial.
    Bill Jackson

    26. The U, V and W Polynomials.
    Steven Noble

    27. Valuative invariants on matroid basis polytopes Topological Extensions of the Tutte Polynomial.
    Sergei Chmutov

    28. The Tutte polynomial of Matroid Perspectives.
    Emeric Gioan

    29. Hyperplane Arrangements and the Finite Field Method.
    Federico Ardila

    30. Some Algebraic Structures related to the Tutte Polynomial.
    Michael J. Falk, Joseph P.S. Kung

    31. The Tutte Polynomial of Oriented Matroids.
    Emeric Gioan

    32. Valuative Invariants on Matroid Basis Polytopes.
    Michael J. Falk, Joseph P.S. Kung

    33. Non-matroidal Generalizations.
    Gary Gordon, Elizabeth McMahon

    VI History.

    34. The History of Tutte–Whitney Polynomials.
    Graham Farr


    Joanna A. Ellis-Monaghan is a professor of discrete mathematics at the Korteweg - de Vries Instituut voor Wiskunde at the Universiteit van Amsterdam. Her research focuses on algebraic combinatorics, especially graph polynomials, as well as applications of combinatorics to DNA self-assembly, statistical mechanics, computer chip design, and bioinformatics. She also has an interest in mathematical pedagogy. She has published over 50 papers in these areas.

    Iain Moffatt is a professor of mathematics in Royal Holloway, University of London. His main research interests lie in the interactions between topology and combinatorics. He is especially interested in graph polynomials, topological graph theory, matroid theory, and knot theory. He has written more than 40 papers in these areas and is also the author of the book An Introduction to Quantum and Vassiliev Knot invariants.

    Ellis-Monaghan and Moffatt have authored several papers on the Tutte polynomial and related graph polynomials together as well as the book Graphs on surfaces: Dualities, Polynomials, and Knots.

    "This is a comprehensive reference text on the Tutte polynomial, including its applications and extensions. The book consists of 34 relatively short chapters written by different contributing authors. The individual contributors present the most important theorems in their respective fields and illustrate them with examples. Each chapter ends with a list of open problems. Two brief introductory chapters by the editors—Ellis-Monaghan (Univ. of Amsterdam) and Moffatt (Royal Holloway, University of London)—cover the basic definitions and computational results for Tutte polynomials. The next two-thirds of the book are devoted to applications and extensions, that is, uses and occurrences of Tutte polynomials outside graph theory or matroid theory. Hyperplane arrangements, quantum field theory, network reliability, the sandpile model, and chipfiring games are a few examples of the topics treated. The book concludes with a chapter on the history of the subject written by Graham Farr. It follows from the nature of the volume (i.e., no proofs, no exercises, very broad topical coverage, and more than 50 authors) that classroom use of the book is unlikely. Nonetheless, this work is likely to become the most frequently consulted reference on Tutte polynomials."

    Summing Up: Highly recommended. Graduate students and faculty.

    -Choice Review