Sign up to our mailing list by sending a blank email to invariantsociety-subscribe@maillist.ox.ac.uk

The Tutte Polynomial and Computational Complexity

Leslie Goldberg

Date Icon Week 7, Tuesday 3 March HT 2015
Time Icon 8:15pm

The Tutte polynomial is an interesting two-variable graph polynomial defined by a deletion-contraction recurrence. I will first define a specialisation, the chromatic polynomial, which was introduced earlier by Birkhoff as an approach to the 4-colour problem. I will then define Tutteā€™s polynomial and show how it captures interesting graph properties. I will discuss the problem of computationally evaluating the polynomial at a fixed point (x,y), given an input graph. I will use this a means of introducing the research area of computational complexity theory and I will finish by telling you a little bit about what is known about the complexity of evaluating the Tutte polynomial (exactly and approximately) and the complexity of determining its sign.