Abstract :

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