Evaluating the Tutte Polynomial for Graphs of Bounded Tree-Width
Evaluating the Tutte Polynomial for Graphs of Bounded Tree-Width
It is known that evaluating the Tutte polynomial, T(G; x, y), of a graph, G, is #P-hard at all but eight specific points and one specific curve of the (x, y)-plane. In contrast we show that if k is a fixed constant then for graphs of tree-width at most k …