The classical Tutte polynomial is a two-variable graph polynomial with the universal property that essentially any graph invariant that can be computed via a deletion-contraction reduction must be an evaluation of it. Many applications that can be modeled graph theoretically have natural deletion-contraction reductions, and this is part of the appeal of the Tutte polynomial. The classical Tutte polynomial was fully generalized using colored graphs by Zaslavsky (1992) and Bollobas and Riordan (1999).
However, graph polynomials can be defined by techniques other than deletion-contraction. In 1987, Jaeger introduced transition polynomials of 4-regular graphs to unify polynomials given by vertex reconfigurations very similar to the skein relations of knot theory. These include the Martin polynomial (restricted to 4-regular graphs), the Kauffman bracket, and, for planar graphs via their medial graphs, the Penrose and classical Tutte polynomials.
Recently I constructed, in joint work with Irasema Sarmiento, generalized transition polynomials which extend the transition polynomials of Jaeger to arbitrary Eulerian graphs, and introduced pair weightings which function analogously to the colored edges in the generalized Tutte polynomial. The generalized transition polynomial and the generalized Tutte polynomial are related for planar graphs in much the same way as are Jaeger's transition polynomial and the classical Tutte polynomial.
Moreover, the generalized transition polynomials are Hopf algebra maps. Thus, the comultiplication and antipode give recursive identities for generalized transition polynomials. Extension of these results to the generalized Tutte polynomial and knot invariants is the subject of current research.