Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, October 14, 2003, 12:15 pm
Duration: This information is not available in the database
Location: This information is not available in the database
Speaker: Michael Krivelevich (Tel Aviv University)
The chromatic number of a graph is one of the most central and well
studied notions in graph theory. In this talk we discuss its
very natural generalization, the choice number of a graph.
The concept of list coloring of graphs was introduced by Vizing and
independently by Erdos, Rubin and Taylor in the late seventies. The
choice number (or the list chromatic number) of a graph G=(V,E) is
the minimum integer k such that for every assignment of a list of k
colors to every vertex v of G (where lists for different vertices
may be different), there is a choice function f, choosing for each
vertex a color from its list in such a way that no edge of G is
monochromatic. After twenty five years of study the choice number
appears to be a much more complicated quantity than the chromatic
number, and much less is known about it.
In recent years there has been a significant progress in many diverse questions, pertaining to the area of list coloring. I will survey some of these developments, with a particular emphasis on comparison of choice number and chromatic number and list coloring properties of random graphs.
Basically no previous experience with graph coloring will be assumed.
Automatic MiSe System Software Version 1.4803M | admin login