Graph polynomials and their applications II: Interrelations and interpretations

Understand

This paper surveys a comprehensive, although not exhaustive, sampling of graph polynomials with the goal of providing a brief overview of a variety of techniques defining a graph polynomial and then for decoding the combinatorial information it contains.

• The polynomials we discuss here are not generally specializations of the Tutte polynomial, but they are each in some way related to the Tutte polynomial, and often to one another.
• We emphasize these interrelations and explore how an understanding of one polynomial can guide research into others.
• We also discuss multivariable generalizations of some of these polynomials and the theory facilitated by this.