Types of embedded graphs and their Tutte polynomials

DOI10.1017/S0305004119000161arXiv2212.14233WikidataQ127566675 ScholiaQ127566675MaRDI QIDQ6508275

Author name not available (Why is that?)

Abstract: 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 identify a universal deletion-contraction invariant (i.e., a `Tutte polynomial') for each class. We relate these to graph polynomials in the literature, including the Bollob'as--Riordan, Krushkal, and Las Vergnas polynomials, and give state-sum formulations, duality relations, deleton-contraction relations, and quasi-tree expansions for each of them.

Mathematics Subject Classification ID

No records found.

This page was built for publication: Types of embedded graphs and their Tutte polynomials

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6508275)