Evaluations of topological Tutte polynomials

DOI10.1017/S0963548314000571zbMATH Open1371.05134arXiv1108.3321OpenAlexW2962772530MaRDI QIDQ5364243FDOQ5364243

Authors: Joanna A. Ellis-Monaghan, Iain Moffatt 

Publication date: 4 October 2017

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

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

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

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

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (15)

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

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)