June 2, 2008
Humboldt-Universität zu Berlin
Institut für Informatik
Rudower Chaussee 25
Lecture - 14:15
Map and graph coloring problems have been motivated by the famous Four-Color Problem. Even today, three decades after the Four-Color Problem has been solved, new fundamental theorems about colorings of graphs embedded in surfaces are discovered. They are one of the most active areas in graph theory today.
In the first half of the talk, we shall survey recent progress, mostly due to Thomassen, Mohar, Thomas, and myself.
The topic includes "list-coloring". An interesting variant of the classical problem of properly coloring the vertices of a graph with the minimum possible number of colors arises when one imposes some restrictions on the colors or the number of colors available to particular vertices. This variant received a considerable amount of attention by many researchers, and that led to several beautiful conjectures and results. This subject, known as list-coloring, was first introduced in the second half of the 1970s, in two papers by Vizing and independently by Erdös, Rubin and Taylor. In the second half of the talk, we discuss 5-list-colorability of graphs on a fixed surface. We also discuss the complexity issue of list-coloring graphs on surfaces.
Some of work is joint work with Carsten Thomassen and Bojan Mohar.
Colloquium - 16:00
Szemeredi's regularity lemma states that every graph can be well approximated by randomly looking bipartite graphs. It led to many exciting applications in graph theory and in computer science. There is also a straightforward generalization to uniform hypergraphs, called weak hypergraph regularity lemma. It has been of less use so far.
The hypergraph of the Fano plane (projective plane on 7 points) is the 3-uniform hypergraph on 7 vertices, which hyperedges are lines of the Fano plane. In 2005 Keevash/Sudakov and Füredi/Simonovits determined the unique extremal 3-uniform hypergraph that does not contain a Fano plane: it is the balanced, complete, bipartite hypergraph. Using this result and recent developments in the applications of the weak hypergraph regularity lemma, we show that almost every 3-uniform hypergraph that does not contain a Fano plane is bipartite. This is joint work with Mathias Schacht.