A Penrose polynomial for embedded graphs

DOI10.1016/J.EJC.2012.06.009MaRDI QIDQ691594zbMATH OpenOpenAlexFDO

Authors Joanna A. Ellis-Monaghan, Iain Moffatt

Publication date 3 December 2012

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1106.5279

zbMATH Keywords

chromatic polynomialstransition polynomialribbon group action

Mathematics Subject Classification ID

Graph polynomials (05C31) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Planar graphs; geometric and topological aspects of graph theory (05C10) Relations of low-dimensional topology with graph theory (57M15)

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.

Recommendations

• The Penrose polynomial of a plane graph
• scientific article; zbMATH DE number 1924327
• On the number of 3-edge colorings of cubic graphs
• The Penrose polynomial of graphs and matroids
• scientific article; zbMATH DE number 1743838

Cited in

(16)

• Penrose's ideas on the 4-color-problem
• New dualities from old: generating geometric, Petrie, and Wilson dualities and trialities of ribbon graphs
• The Penrose polynomial of graphs and matroids
• Evaluations of topological Tutte polynomials
• On the number of 3-edge colorings of cubic graphs
• Planar diagrams for local invariants of graphs in surfaces
• Orienting transversals and transition polynomials of multimatroids
• scientific article; zbMATH DE number 1743838 (Why is no real title available?)
• scientific article; zbMATH DE number 1924327 (Why is no real title available?)
• The excluded 3-minors for vf-safe delta-matroids
• Twisted duality for embedded graphs
• On embeddings of Grassmann graphs in polar Grassmann graphs
• On ribbon graphs and virtual links
• Hopf algebras and Tutte polynomials
• The Penrose polynomial of a plane graph
• Edge colourings and topological graph polynomials

This page was built for publication: A Penrose polynomial for embedded graphs

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