Graph Polynomials: From Recursive Definitions To Subset Expansion Formulas

Benny Godlin, Emilia Katz, Johann A. Makowsky

Many graph polynomials, such as the Tutte polynomial, the interlace polynomial and the matching polynomial, have both a recursive definition and a defining subset expansion formula…