Graph polynomials from simple graph sequences
Andrew Goodall
Charles University, Prague
Charles University, Prague
2014/04/14 Monday 4PM-5PM
Room 1409
Room 1409
The chromatic polynomial evaluated at a positive integer n is equal to the number of homomorphisms to the complete graph on n vertices. Many important graph polynomials are likewise determined by counting homomorphisms to a sequence of (multi) graphs, such as the Tutte polynomial and the independence polynomial. We give a powerful construction that produces graph polynomials in this way from sequences of simple graphs. It uses just two fundamental operations (disjoint union and interpretations of relational structures) and starts from a simple set of building blocks (coloured transitive tournaments).This will be illustrated by many examples, some of whose combinatorial properties have been well explored (such as that of the chromatic polynomial), but most of which are new. This is joint work with Jarik Nesetril and Patrice Ossona de Mendez.</p>