Abstract
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 wellbehaved 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 deletioncontraction 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 wellknown 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.
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 deletioncontraction 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 wellknown 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.
Original language  English 

Qualification  Ph.D. 
Awarding Institution 

Supervisors/Advisors 

Award date  1 Mar 2024 
Publication status  Unpublished  2024 
Keywords
 Tutte polynomial
 Embedded graph
 Ribbon graph
 Pseudosurfaces
 Krushkal polynomial
 Las Vergnas Polynomial
 BollobasRiordan Polynomial
 Matroid
 Deltamatroid
 Multimatroid
 Royal Holloway
 Maya Thompson
 Topological graph