<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 13 Issue 3" %>
Expansions for the Bollob´as-Riordan Polynomial of Separable Ribbon Graphs
Stephen Huggett1 and Iain Moffatt2
1School of Mathematics and Statistics, University of Plymouth, Drake Circus, Plymouth PL4 8AA, UK
2Department of Mathematics and Statistics, University of South Alabama, Mobile, AL 36688, USA
Annals of Combinatorics 15 (4) pp.675-706 December, 2011
AMS Subject Classification: 05C31; 05C10, 57M15
We define 2-decompositions of ribbon graphs, which generalize 2-sums and tensor products of graphs. We give formulae for the Bollob´as-Riordan polynomial of such a 2-decomposition, and derive the classical Brylawski formula for the Tutte polynomial of a tensor product as a (very) special case. This study was initially motivated from knot theory, and we include an application of our formulae to mutation in knot diagrams.
Keywords: ribbon graph; embedded graph; 2-sum; tensor product; Tutte polynomial; Bollobás- Riordan polynomial; Ribbon graph polynomial; Jones polynomial


1. Bollobás, B.: Modern Graph Theory. Springer-Verlag, New York (1998)

2. Bollobás, B., Riordan, O.: A polynomial invariant of graphs on orientable surfaces. Proc. London Math. Soc. 83, 513–531 (2001)

3. Bollobás, B., Riordan, O.: A polynomial of graphs on surfaces. Math. Ann. 323(1), 81–96 (2002)

4. Brylawski, T.H.: The Tutte polynomial I: general theory. In: Barlotti, A. (ed.) Matroid Theory and Its Applications, pp. 125–275. Liguori, Naples (1982)

5. Brylawski, T.H., Oxley, J.G.: The Tutte polynomial and its applications. In: White, N. (ed.) Matroid Applications, pp. 123–225. Cambridge Univ. Press, Cambridge (1992)

6. Chmutov, S., Pak, I.: The Kauffman bracket of virtual links and the Bollobás-Riordan polynomial. Mosc. Math. J. 7(3), 409–418 (2007)

7. Chmutov, S., Voltz, J.: Thistlethwaite’s theorem for virtual links. J. Knot Theory Ramifications 17(10), 1189–1198 (2008)

8. Dasbach, O.T., Futer, D., Kalfagianni, E., Lin, X.-S., Stoltzfus, N.W.: The Jones polynomial and graphs on surfaces. J. Combin. Theory Ser. B 98(2), 384–399 (2008)

9. Goldberg, L.A., Jerrum, M.: Inapproximability of the Tutte polynomial. Inform. and Comput. 206(7), 908–929 (2008)

10. Gross, J.L., Tucker, T.W.: Topological Graph Theory. John Wiley & Sons, Inc., New York (1987)

11. Huggett, S.: On tangles and matroids. J. Knot Theory Ramifications 14(7), 919–929 (2005)

12. Jaeger, F.: Tutte polynomials and link polynomials. Proc. Amer. Math. Soc. 103(2), 647–654 (1988)

13. Jaeger, F., Vertigan, D.L., Welsh, D.J.A.: On the computational complexity of the Jones and Tutte polynomials. Math. Proc. Cambridge Philos. Soc. 108(1), 35–53 (1990)

14. Jerrum, M.: Approximating the Tutte polynomial. In: Grimmett, G.,McDiarmid, C. (eds.) Combinatorics, Complexity, and Chance: A Tribute to Dominic Welsh, pp. 144–161. Oxford University Press, Oxford (2007)

15. Kauffman, L.H.: State models and the Jones polynomial. Topology 26(3), 395–407 (1987)

16. Loebl, M., Moffatt, I.: The chromatic polynomial of fatgraphs and its categorification. Adv. Math. 217(4), 1558–1587 (2008)

17. Moffatt, I.: Knot invariants and the Bollobás-Riordan polynomial of embedded graphs. European J. Combin. 29(1), 95–107 (2008)

18. Seymour, P.D.: Decomposition of regular matroids. J. Combin. Theory Ser. B 28(3), 305–359 (1980)

19. Sokal, A.D.: The multivariate Tutte polynomial (alias Potts model) for graphs and matroids. In: Webb, B.S. (ed.) Surveys in Combinatorics, 2005, pp. 173–226. Cambridge Univ. Press, Cambridge (2005)

20. Thistlethwaite,M.B.: A spanning tree expansion of the Jones polynomial. Topology 26(3), 297–309 (1987)

21. Traldi, L.: A dichromatic polynomial for weighted graphs and link polynomials. Proc. Amer. Math. Soc. 106(1), 279–286 (1989)

22. Woodall, D.R.: Tutte polynomial expansions for 2-separable graphs. Discrete Math. 247(1-3), 201–213 (2002)