Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, December 11, 2008, 12:15 pm
Duration: This information is not available in the database
Location: OAT S15/S16/S17
Speaker: Dan Hefetz
Alon and Tarsi have introduced an algebraic technique for proving upper bounds on the choice number of graphs; the upper bound on the choice number of $G$ obtained via their method, was later coined the Alon-Tarsi number of $G$ and was denoted by $AT(G)$. In the talk I will relate this parameter to a certain weighted sum of the proper colorings of $G$. Other than the appealing notion of obtaining upper bounds on the choice number of a graph via its proper colorings (in some sense), this result has many applications. Some of them are known; for these we give unified, and often also simpler and shorter proofs; and some are new.
Most of the first talk will be devoted to introducing chromatic, choice, and Alon-Tarsi numbers of graphs. In the second talk I will state the main result and some of its applications.
Automatic MiSe System Software Version 1.4803M | admin login