The Tutte polynomial characterizes simple outerplanar graphs

Andrew Goodall

Abstract

In this talk I shall describe some recent joint work with Anna de Mier and Marc Noy (UPC, Barcelona) and Steve Noble (Brunel, London).

The title tells it all, but here's an elaboration:

The Tutte polynomial T(G;x,y) of a graph G is a polynomial that encodes much combinatorial information about G, including the girth of G, the number of k-cliques in G and the number of proper vertex k-colourings of G. On the other hand, there is a pair of graphs with different degree sequences that have the same Tutte polynomial, and also non-planar G and planar H such that T(G;x,y)=T(H;x,y).

The Tutte polynomial of any forest with m edges is equal to x^m. Although this means the Tutte polynomial cannot distinguish any pair of forests on the same number of edges, it is on the other hand true that if T(G;x,y) = x^m then G must be a forest on m edges. In this sense the Tutte polynomial characterizes the class