Combinatorics Seminar
When: Sunday, December 21, 10am
Where: Schreiber 309
Speaker: Dan Hefetz, Swiss Federal Institute of Technology (ETH)
Title: Weighted colorings and Alon-Tarsi choosability
Abstract:
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.