## Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

# Mittagsseminar (in cooperation with M. Ghaffari, A. Steger and B. Sudakov)

 Mittagsseminar Talk Information

Date and Time: Thursday, December 11, 2008, 12:15 pm

Duration: This information is not available in the database

Location: CAB G51

Speaker: Dan Hefetz

## Weighted colorings and Alon-Tarsi choosability (Part II)

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.

Information for students and suggested topics for student talks