On 06.05.2010 at 12:20 in S6, there is the following noon lecture:
The Tutte polynomial characterizes simple outerplanar graphs
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
Webmaster: kamweb.mff.cuni.cz Modified: 19. 10. 2010