# The Tutte Polynomial and Computational Complexity

## Leslie Goldberg

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.