Mittagsseminar (in cooperation with J. Lengler, A. Steger, and D. Steurer)

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)

List Coloring of Graphs

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.

Upcoming talks     |     All previous talks     |     Talks by speaker     |     Upcoming talks in iCal format (beta version!)

Previous talks by year:   2025  2024  2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login