June 2, 2008
Humboldt-Universität zu Berlin
Institut für Informatik
Rudower Chaussee 25
room 4.112.
Lecture - 14:15
Abstract:
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
Abstract:
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.