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 polynomialsribbon group actiontransition polynomial

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph polynomials (05C31) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) 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

(21)

• On the number of 3-edge colorings of cubic graphs
• The Penrose polynomial of a plane graph
• Penrose's ideas on the 4-color-problem
• Hopf algebras and Tutte polynomials
• The excluded 3-minors for vf-safe delta-matroids
• On ribbon graphs and virtual links
• The Penrose polynomial of graphs and matroids
• Twisted duality for embedded graphs
• scientific article; zbMATH DE number 1743838 (Why is no real title available?)
• Edge colourings and topological graph polynomials
• scientific article; zbMATH DE number 1924327 (Why is no real title available?)
• Planar diagrams for local invariants of graphs in surfaces
• Evaluations of topological Tutte polynomials
• New dualities from old: generating geometric, Petrie, and Wilson dualities and trialities of ribbon graphs
• Orienting transversals and transition polynomials of multimatroids
• A Negami-type splitting formula for the Jones and ribbon graph polynomials
• Multi-virtual knot theory
• An activities expansion of the transition polynomial of a multimatroid
• A state sum for the total face color polynomial
• Tensor product formulas for the Bollobás-Riordan and Krushkal polynomials
• On embeddings of Grassmann graphs in polar Grassmann graphs

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)