
Discrete Mathematics and Optimization Seminar

Feb. 9th, 2009
Weighted colorings and AlonTarsi 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
AlonTarsi 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
AlonTarsi numbers of graphs. In the second part I will state the main
result and some of its applications.



