A Penrose polynomial for embedded graphs

Abstract

We extend the Penrose polynomial, originally defined only for plane graphs, to graphs embedded in arbitrary surfaces. Considering this Penrose polynomial of embedded graphs leads to new identities and relations for the Penrose polynomial which can not be realized within the class of plane graphs. In particular, by exploiting connections with the transition polynomial and the ribbon group action, we find a deletion-contraction-type relation for the Penrose polynomial. We relate the Penrose polynomial of an orientable checkerboard colourable graph to the circuit partition polynomial of its medial graph and use this to find new combinatorial interpretations of the Penrose polynomial. We also show that the Penrose polynomial of a plane graph G can be expressed as a sum of chromatic polynomials of twisted duals of G. This allows us to obtain a new reformulation of the Four Colour Theorem.

References in corpus (4)

• The multivariate signed Bollobas-Riordan polynomial
• Knot invariants and the Bollobas-Riordan polynomial of embedded graphs
• Twisted duality for embedded graphs
• Partial duality and Bollobas and Riordan's ribbon graph polynomial

Cited by in corpus (8)

• On the interplay between embedded graphs and delta-matroids
• Matroids, Delta-matroids and Embedded Graphs
• Quaternary Bicycle Matroids and the Penrose Polynomial for Delta-Matroids
• Planar diagrams for local invariants of graphs in surfaces
• Hopf algebras and Tutte polynomials
• New Dualities From Old: generating geometric, Petrie, and Wilson dualities and trialites of ribbon graphs
• Orienting Transversals and Transition Polynomials of Multimatroids
• The excluded 3-minors for vf-safe delta-matroids