Title: Alon–Tarsi Numbers for Multigraphs via the Interpolation Formula

Speaker: Jakub Kozik, JagiellonianUniversity (Krakow, Poland)

Abstract: We are going to work with algebraic approach to graph coloring known as the Alon–Tarsi method. The Alon–Tarsi number AT(G) of a graph, originally defined via the graph polynomial, provides an upper bound on the list‑chromatic number and belongs to the standard toolbox of the coloring theory. A classical reformulation uses graph orientations: the inequality AT(G)<k can be certified by an orientation of G in which every vertex has outdegree at most k−1, and the numbers of its even and odd eulerian subgraphs differ. Another viewpoint relies on an interpolation formula expressing the coefficients of the graph polynomial through its values on a sufficiently large grid.  This leads to situations where bounds on the choice number can be deduced by analyzing colorings from a single fixed list assignment. We will discuss how this perspective can be used to extend classical results on line‑graph colorings to their multigraph analogues.

 

---

Location: A1046

Date and Time: Wednesday, Mar. 18 at 04:10 PM - 05:10 PM (NDT)

---