Discrete Mathematics and Optimization Seminar
Feb. 9th, 2009
Weighted colorings and Alon-Tarsi choosability.
Dan Hefetz
ETH Zurich
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.

In the first part of the talk I will introduce chromatic, choice, and Alon-Tarsi numbers of graphs. In the second part I will state the main result and some of its applications.