Abstract
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. We conclude with two
examples, one from biology and one from physics, that illustrate the
applicability of graph polynomials in other fields.
This is the second chapter of a two chapter series, and concludes Graph
Polynomials and Their Applications I: The Tutte Polynomial, <a href="/abs/0803.3079">arXiv:0803.3079</a>
Users
Please
log in to take part in the discussion (add own reviews or comments).