Evaluations of Topological Tutte Polynomials

Joanna A. Ellis-Monaghan, Iain Moffatt

Research output: Contribution to journalArticlepeer-review

130 Downloads (Pure)

Abstract

We find new properties of the topological transition polynomial of embedded graphs, Q(G). We use these properties to explain the striking similarities between certain evaluations of Bollobás and Riordan's ribbon graph polynomial, R(G), and the topological Penrose polynomial, P(G). The general framework provided by Q(G) also leads to several other combinatorial interpretations these polynomials. In particular, we express P(G), R(G), and the Tutte polynomial, T(G), as sums of chromatic polynomials of graphs derived from G, show that these polynomials count k-valuations of medial graphs, show that R(G) counts edge 3-colourings, and reformulate the Four Colour Theorem in terms of R(G). We conclude with a reduction formula for the transition polynomial of the tensor product of two embedded graphs, showing that it leads to additional relations among these polynomials and to further combinatorial interpretations of P(G) and R(G).
Original languageEnglish
Pages (from-to)556-583
Number of pages28
JournalCombinatorics, Probability and Computing
Volume24
Issue number3
Early online date10 Oct 2014
DOIs
Publication statusPublished - May 2015

Cite this