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