# Noon lecture

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

On 22.10.2009 at 12:20 in corridor, there is the following noon lecture:

# Graph homomorphisms and contraction-deletion invariants

## Andrew Goodall

## Mathematical Institute, Oxford United Kingdom

## Abstract

In this talk I shall describe some recent joint work with Delia Garijo and Jarik Nešetřil.

The function hom(G,H) counting the number of homomorphisms from a multigraph G to a multigraph H extends in a natural way to edge-weighted graphs H.

A generalized Tutte--Grothendieck invariant (TG-invariant for short) is a graph parameter that satisfies a contraction-deletion recurrence of a form similar to that satisfied by the chromatic polynomial and by the Tutte polynomial T(G;x,y). A TG-invariant takes the form h(G)T(G;x,y), where the prefactor h(G) is a product of exponentials in the rank, size and order of G. Many combinatorial interpretations of Tutte polynomial evaluations have been proved by establishing the validity of a contraction-deletion recurrence, for example Stanley's result that T(G;2,0) counts the number of acyclic

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