Strong Tutte Functions of Matroids and Graphs
Thomas Zasĺavsky · Transactions of the American Mathematical Society · 1992
A strong Tutte function of matroids is a function of finite matroids which satisfies $F({M_1} \oplus {M_2}) = F({M_1})F({M_2})$ and $F(M) = {a_e}F(M\backslash e) + {b_e}F(M/e)$ for $e$ not a loop or coloop of $M$, where ${a_e}$, ${b_e}$ are scalar parameters depending only on $e$. We classify strong Tutte functions of all matroids into seven types, generalizing Brylawski’s classification of Tutte-Grothendieck invariants. One type is, like Tutte-Grothendieck invariants, an evaluation of a rank polynomial; all types are given by a Tutte polynomial. The classification remains valid if the domain is any minor-closed class of matroids containing all three-point matroids. Similar classifications hold for strong Tutte functions of colored matroids, where the parameters depend on the color of $e$, and for strong Tutte functions of graphs and edge-colored graphs whose values do not depend on the attachments of loops. The latter classification implies new characterizations of Kauffman’s bracket polynomials of signed graphs and link diagrams.