• Calendar

December 23, Tuesday
12:00 – 14:00

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 emph{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.