Lectures and Colloquia during the semester

**December 17, 2001**

Freie Universität Berlin - Institut für
Informatik

Takustraße 9

14195 Berlin

Room 005
- map -

**Lecture - 14:15**

### 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.

[home] -
[up] -
[top]