On two generalizations of the Alon-Tarsi polynomial method

Abstract: In a seminal paper, Alon and Tarsi have introduced an algebraic
technique for proving upper bounds on the choice number of graphs (and thus,
in particular, upper bounds on their chromatic number). 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). They
have provided a combinatorial interpretation of this parameter in terms of
the eulerian sub-digraphs of an appropriate orientation of G.
Shortly afterwards, for the special case of line
graphs of d-regular d-edge-colorable graphs, Alon gave another
interpretation of AT(G), this time in terms of the signed d-colorings of
the line graph. In the talk I will generalize both results.
I will then use these results to prove some choosability results.
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 two generalizations as well as
some applications.