Types of embedded graphs and their Tutte polynomials. / Huggett, Stephen; Moffatt, Iain.

In: Mathematical Proceedings of the Cambridge Philosophical Society, 02.07.2019, p. 1-43.

Research output: Contribution to journalArticle

E-pub ahead of print


  • Accepted Manuscript

    Accepted author manuscript, 9 MB, PDF-document

    Embargo ends: 2/01/20


We take an elementary and systematic approach to the problem of extending the Tutte polynomial to the setting of embedded graphs. Four notions of embedded graphs arise naturally when considering deletion and contraction operations on graphs on surfaces. We give a description of each class in terms of coloured ribbon graphs. We then iden- tify a universal deletion-contraction invariant (i.e., a ‘Tutte polynomial’) for each class. We relate these to graph polynomials in the literature, including the Bollobas–Riordan, Krushkal, and Las Vergnas polynomials, and give state-sum formulations, duality rela- tions, deleton-contraction relations, and quasi-tree expansions for each of them.
Original languageEnglish
Pages (from-to)1-43
Number of pages43
JournalMathematical Proceedings of the Cambridge Philosophical Society
Early online date2 Jul 2019
Publication statusE-pub ahead of print - 2 Jul 2019
This open access research output is licenced under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.

ID: 33736367