The topological Tutte polynomials of Bollobás and
Riordan: properties and relations to other graph polynomials
Irasema Sarmiento (Università di Roma "Tor Vergata")
Joint work with Joanna Ellis-Monaghan
In [BR01], [BR02], Bollobás and Riordan defined analogs of the Tutte polynomial for graphs embedded in surfaces, thus encoding topological information lost in the classical Tutte polynomial. We provide a `recipe theorem' for these polynomials and use it to relate them to several interesting polynomials such as the generalized transition polynomial, and the Kauffman bracket.
The relationship between the generalized transition polynomial and the topological Tutte polynomial extends a result of [Jae90] from planar graphs to arbitrary graphs.
We also visit the Kauffman bracket in light of these relationships and that established between it and the topological Tutte polynomial in [CP]. We use the recipe theorem to extend the duality relation for the topological Tutte polynomial in [BR02] from one degree of freedom to two, giving a natural extension of the duality of the classical Tutte polynomial.
[BR01] B. Bollobás, O. Riordan, A polynomial invariant of graphs on orientable surfaces, Proc. Lond. Math. Soc., III Ser. 83, No. 3, 513-531 (2001).
[BR02] B. Bollobás, O. Riordan, A polynomial of graphs on surfaces, Math. Ann. 323, 81-96 (2002).
[CP] S. Chmutov, I. Pak, The Kauffman bracket and the Bollobás-Riordan polynomial of ribbon graphs, preprint.
[E-MS02] J. A. Ellis-Monaghan, I. Sarmiento, Generalized transition polynomials, Congr. Numer. 155 (2002) 57-69.
[Jae90] F. Jaeger, On transition polynomials of 4-regular graphs, In: Cycles and Rays (Hahn et al, eds.) Kluwer (1990), 123-150.