Coloured Tutte polynomials and Kauffman brackets for graphs of bounded tree width

AbstractTutte polynomials are important graph invariants with rich applications in combinatorics, topology, knot theory, coding theory and even physics. The Tutte polynomial T(G,X,Y) is a polynomial in Z[X,Y] which depends on a graph G. Computing the coefficients of T(G,X,Y), and even evaluating T(G,X,Y) at specific points (x,y) is ♯P hard by a result of Jaeger et al. (Math. Proc. Cambridge Philos. Soc. 108 (1989) 35). On the other hand, Andrzejak (Discrete Math. 190 (1998) 39–54) and Noble (Combin. Probab. Comput. 7 (1998) 307–321) have shown independently, that, if G is a graph of bounded tree width, computing T(G,X,Y) can be done in polynomial time. We extend this result to the signed Tutte polynomials introduced in 1989 by Kauffman and the colored Tutte polynomials introduced in 1999 by Bollobas and Riordan. This allows us to prove similar results for the Jones polynomials and Kauffman brackets for knots and links which have a signed graph presentation of bounded tree width. Jones polynomials and Kauffman polynomials are the most prominent invariants of knot theory. For alternating links, they are easily computable from the Tutte polynomials of the signed graph representing the link by a result of Thistlethwaite (1988). For general links one has to use the colored Tutte polynomial instead. Knots and links can be presented as labeled planar graphs. The tree width of a link L is defined as the tree width of its graphical presentation D(L) as crossing diagrams. We show that for (not necessarily alternating) knots and links of tree width at most k, even the Kauffman square bracket [L] introduced by Bollobas and Riordan can be computed in polynomial time. Hence, the classical Kauffman bracket 〈L〉 and the Jones polynomial of links of tree width at most k are computable in polynomial time. Our proof is based on, but extends considerably previous work by B. Courcelle, U. Rotics and the author. It also gives a new proof of the result for Tutte polynomials and generalizes to a wide class of polynomials defined as generating functions definable in Monadic Second Order Logic with order, but invariant under it