Evaluations of topological Tutte polynomials

DOI10.1017/S0963548314000571MaRDI QIDQ5364243zbMATH OpenOpenAlexFDO

Authors Joanna A. Ellis-Monaghan, Iain Moffatt

Publication date 4 October 2017

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Graph polynomials (05C31) Planar graphs; geometric and topological aspects of graph theory (05C10)

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'as 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)$.

Recommendations

• Edge colourings and topological graph polynomials
• Topological extensions of the Tutte polynomial
• A recipe theorem for the topological Tutte polynomial of Bollobás and Riordan
• A Penrose polynomial for embedded graphs
• Bollobás-Riordan and relative Tutte polynomials

Cites work

• scientific article; zbMATH DE number 4214039 (Why is no real title available?)
• scientific article; zbMATH DE number 1933265 (Why is no real title available?)
• scientific article; zbMATH DE number 5251649 (Why is no real title available?)
• scientific article; zbMATH DE number 3344105 (Why is no real title available?)
• A Penrose polynomial for embedded graphs
• A polynomial invariant of graphs on orientable surfaces
• A polynomial of graphs on surfaces
• A recipe theorem for the topological Tutte polynomial of Bollobás and Riordan
• Expansions for the Bollobás-Riordan polynomial of separable ribbon graphs
• Generalized duality for graphs on surfaces and the signed Bollobás-Riordan polynomial
• Knot invariants and the Bollobás-Riordan polynomial of embedded graphs
• Le Polynôme De Martin D'un Graphe Eulerien
• New results for the Martin polynomial
• On Tutte polynomials and cycles of plane graphs
• Operators over regular maps
• Parallel connections and coloured Tutte polynomials
• Penrose's ideas on the 4-color-problem
• Separability and the genus of a partial dual
• The Jones polynomial and graphs on surfaces
• The Penrose polynomial of a plane graph
• The Tutte polynomial. I: General theory
• Tutte polynomial expansions for 2-separable graphs
• Tutte polynomials computable in polynomial time
• Twisted duality for embedded graphs

Cited in

(15)

• A recipe theorem for the topological Tutte polynomial of Bollobás and Riordan
• Topological extensions of the Tutte polynomial
• Matroids with different configurations and the same \(\mathcal{G} \)-invariant
• New dualities from old: generating geometric, Petrie, and Wilson dualities and trialities of ribbon graphs
• Tutte polynomial of tensor product graph and its applications
• On terminal forms for topological polynomials for ribbon graphs: the \(N\)-petal flower
• On the evaluation at (3,3) of the Tutte polynomial of a graph
• Matroids, delta-matroids and embedded graphs
• Hopf algebras and Tutte polynomials
• Bollobás-Riordan and relative Tutte polynomials
• Edge colourings and topological graph polynomials
• scientific article; zbMATH DE number 1933265 (Why is no real title available?)
• Characterization of regular checkerboard colourable twisted duals of ribbon graphs
• The transition matroid of a 4-regular graph: an introduction
• The behavior of Tutte polynomials of graphs under five graph operations and its applications

This page was built for publication: Evaluations of topological Tutte polynomials

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