Announcements

| Event Details

The Alon-Tarsi number of graphs

  • Xuding Zhu

The Alon-Tarsi number of a graph $G$ is the minimum integer $k$ such that
$G$ has an orientation $D$ with maximum out-degree less than $k$ and the number of even Eulerian subdigraphs
of $D$ is distinct from the number of odd Eulerian subdigraphs of $D$. It is known that the choice number and on-line choice number
of $G$ is bounded from above by its Alon-Tarsi number. In this talk, I shall sketch a proof of a recent result that if $G$ is a planar graph,
then the Alon-Tarsi number of $G$ is at most $5$, and moreover, $G$ has a matching $M$ such that $G-M$ has Alon-Tarsi number at most
$4$. The later result implies that every planar graph is $1$-defective $4$-paintable, which generalizes a result of Cushing and Kierstead
that every planar graph is $1$-defective $4$-choosable. The later result is a joint work with Jarolaw Grytczuk