Session B2 - Graph Theory and Combinatorics
July 14, 18:30 ~ 18:55
A Tutte polynomial for graphs embedded on surfaces
University of Amsterdam, The Netherlands - email@example.com
In this talk, we present a graph polynomial for maps (graphs embedded in orientable surfaces) that contains the Las Vergnas polynomial, Bollob\'as-Riordan polynomial and Kruskhal polynomial as specialisations.
The new polynomial invariant of maps is built following Tutte's construction of the dichromate of a graph (that is, the Tutte polynomial) as a unification of the chromatic polynomial and the flow polynomial. In our case, we consider the analogues for maps of the chromatic polynomial (local tensions) and of the flow polynomial (local flows). Hence, by construction, the new polynomial includes among its evaluations the number of local tensions and local flows taking values in any given finite group. Other evaluations include the number of quasi-forests. An extension of the polynomial to graphs embedded on non-orientable surfaces is also discussed.
Joint work with Andrew Goodall (Charles University Prague), Thomas Krajewski (Aix-Marseille Université), Bart Litjens (University of Amsterdam), and Guus Regts (University of Amsterdam)..