Bojan Mohar - University of Ljubljana, Slovenia

Coloring-flow duality for locally planar graphs

Abstract:   It is a classical result of Tutte that a (2-connected) planar graph has a k-coloring if and only if its dual graph admits a nowhere-zero k-flow. For graphs on more general (orientable) surfaces, a coloring still implies existence of a nowhere-zero flow in the dual graph, but the converse is far from being true.

In the talk it will be shown that the duality "almost" works on arbitrary surfaces if the graph is highly locally planar. This is a recent result that involves the notion of circular chromatic number and circular flows which generalize the corresponding classical parameters. It has some interesting consequences in the theory of colorings of graphs on surfaces.

Colloquium - 16:00

Hein van der Holst - Freie Universität Berlin

The interlace polynomial of a graph

Abstract:   Arritia, Bollobás and Sorkin introduced recently a new graph polynomial which they call the interlace polynomial. They define this polynomial in a recursive way, that is, the interlace polynomial of a graph is the sum of the interlace polynomials of two smaller graphs. We will give an explicit (non-recursive) formula for the interlace polynomial and show that for a bipartite graph this polynomial just corresponds to the symmetric Tutte polynomial of a binary matroid. The right framework to study this polynomial seems to be isotropic systems, a combinorial structure introduced by A. Bouchet, and we show that the interlace polynomials are the Martin-Tutte polynomials of a suitable chosen isotropic systems.