Noon lecture

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

On 06.05.2010 at 12:20 in S6, there is the following noon lecture:

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

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

Webmaster: kamweb.mff.cuni.cz         Modified: 19. 10. 2010