** Certificates for Graph Polynomials **

**SPEAKER:** Kerri Morgan, Deakin University

**Date:** Friday 5th October

**Time:** 3:00pm–4:00pm (Talk & Q/A)

**Venue:** Building 8 Level 9 Room 66 (AGR) RMIT City campus

The seminar will be followed by snacks and drinks

All students, staff and visitors are welcome

**ABSTRACT:** The Tutte polynomial 𝑇(𝐺;𝑥,𝑦) of a graph G encapsulates many important properties of a graph such as the number of spanning trees and spanning subgraphs. Many important graph invariants can be obtained from partial evaluations of the Tutte polynomial. These include the chromatic polynomial which counts the number of proper colourings of a graph; the reliability polynomial which gives the probability that a network remains connected under random edge failure; and the flow polynomial which counts the number of nowhere zero flows in a graph. The Tutte polynomial, and any graph polynomial that is a specialisation of the Tutte polynomial, can be computed using deletion/contraction operations.

A certificate is a sequence of expressions using graph properties and algebraic properties. Certificate were introduced by Morgan and Farr to prove results on new types of factorisations of the chromatic polynomial, and have been used to prove results on graph polynomials. In this talk, we demonstrate the use of certificates in proofs of properties of graph polynomials and in constructing counterexamples to some open questions and conjectures.

**BIOGRAPHY:** Dr Kerri Morgan is a lecturer in the School of Information Technology at Deakin University. She is interested in graph theory and algorithms. She is particularly interested in graph polynomials and the connections between the properties of these polynomials and the structural properties of the networks they represent.