Colored Tutte polynomials and Kaufman brackets for graphs of bounded tree width
Colored Tutte polynomials and Kaufman brackets for graphs of bounded tree width
复制标题
有界树宽度图的彩色 Tutte 多项式和考夫曼括号
DOI：
10.1016/j.dam.2004.01.016
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
J. Makowsky
中科院分区：
文献类型：
--
作者：
J. Makowsky
Tutte 多项式是重要的图不变量，在组合学、拓扑学、结论、编码理论甚至物理学中有着丰富的应用。 Tutte 多项式 T(G,X,Y) 是 Z[X,Y] 中的多项式，它取决于图 G。根据 Jaeger 等人的结果，计算 T(G,X,Y) 的系数，甚至在特定点 (x,y) 评估 T(G,X,Y) 都是♯P 困难。 (Math. Proc. Cambridge Philos. Soc. 108 (1989) 35)。另一方面，Andrzejak (Discrete Math. 190 (1998) 39–54) 和 Noble (Combin. Probab. Comput. 7 (1998) 307–321) 独立地表明，如果 G 是有界树宽度的图，则计算 T(G,X,Y) 可以在多项式时间内完成。我们将此结果扩展到 Kauffman 于 1989 年引入的有符号 Tutte 多项式以及 Bollobas 和 Riordan 于 1999 年引入的有色 Tutte 多项式。这使我们能够证明琼斯多项式和考夫曼括号的结和链接的类似结果，这些结和链接具有有界树宽度的符号图表示。琼斯多项式和考夫曼多项式是纽结理论中最突出的不变量。对于交替链接，可以根据 Thistlethwaite (1988) 的结果，根据表示链接的符号图的 Tutte 多项式轻松计算出它们。对于一般链接，必须使用彩色 Tutte 多项式。结和链接可以呈现为带标签的平面图。链接L的树宽度被定义为作为交叉图的其图形表示D(L)的树宽度。我们证明，对于（不一定是交替的）树宽度最多为 k 的结和链接，甚至 Bollobas 和 Riordan 引入的 Kauffman 方括号 [L] 也可以在多项式时间内计算。因此，经典的考夫曼括号<L>和树宽至多为k的链接的琼斯多项式在多项式时间内是可计算的。我们的证明基于 B. Courcelle、U. Rotics 和作者之前的工作，但在很大程度上扩展了它们。它还给出了 Tutte 多项式结果的新证明，并推广到一类广泛的多项式，这些多项式被定义为可在一元二阶逻辑中定义的具有顺序的生成函数，但在其下是不变的。
Tutte 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.