Splitting formulas for Tutte polynomials (Q1362104): Difference between revisions

The Tutte polynomial is a central invariant of a matroid. In particular, many numerical invariants of a matroid can be calculated by evaluating or calculating coefficients of the Tutte polynomial. Moreover, for certain cases there is a close connection between the Tutte polynomial and the Jones and Kauffman polynomial of a link. Thus there is interest in effective algorithms calculating the Tutte polynomial. Unfortunately, it is know that in general computing the Tutte polynomial is \(\#P\)-hard. Nevertheless, there are classes of matroids that admit polynomial time algorithms. The paper under under review provides new instances of matroids for which this is possible. It shows that polynomial time algorithms exist for the class of generalized parallel connections across a \(3\)-point line and for \(3\)-sums of matroids. The concept of generalized parallel connections across a \(3\)-point line is introduced in the paper and extends the usual definition of parallel connection. Other instances of polynomial time algorithms for the Tutte polynomial can be found in the work of \textit{J. G. Oxley} and \textit{D. J. A. Welsh} [Discrete Math. 109, No. 1-3, 185-192 (1992; Zbl 0780.05011)].