Topological Analogues of the Tutte polynomial and their Decompositions

The Tutte polynomial is one of the most influential graph polynomials, whose importance stems from all of the combinatorial and structural information it captures about a graph. Not only that, but the polynomial itself has been subject to much study due to its inherent well-behaved structure and universal nature. In recent years, much interest has been shown in finding an analogue of the Tutte polynomial for graphs embedded in surfaces, resulting in a plethora of topological graph polynomials. There is now an active body of research into these polynomials, the combinatorial information of the embedded graph that they capture, and the properties and structure they exhibit.

This thesis consists of three parts. The first part, Chapters 1–3, paints a picture of what is already known. It provides an overview of topological graphs, how to represent them, and their polynomials, along with notable results across their development in the literature. In the second part, Chapter 4, we unify a recent divergence in the development of topological Tutte polynomials to obtain a new polynomial for embedded graphs that encapsulates the properties of its predecessors. Notably, this new topological graph polynomial possesses a Universality Property, meaning that any graph parameter satisfying a specified set of deletion-contraction relations is a specialisation of this polynomial. A natural consequence of this is a recursive method for counting the number of flows and tensions (i.e., proper colourings) in an embedded graph. The final part, Chapters 5 and 6, provides several tensor product formulae that split well-known topological Tutte polynomials by decomposing a larger graph into smaller graphs that are “multiplied” together. These formulae mirror a result of Brylawski for the Tutte polynomial, which is known for its applications as a computational aid and in understanding the complexity of the Tutte polynomial.