Difference between Alon-Tarsi number and the list chromatic number

Question

The Alon-Tarsi number is the least number $k$ such that the coefficient with degree $d$ of the graph polynomial $P(G)=\prod\limits_{i<j}(x_i-x_j)$,( where $x_i$ corresponds to a vertex and a term $x_i-x_j$ occurs iff there is an edge in the graph from vertex $i\to j$) is nonzero for $d<k$.

By Combinatorial Nullstellensatz, it is known that the list chromatic number of the graph is less than or equal to its Alon-Tarsi number. My question is, are there easy examples of graphs with list chromatic number strictly less than the Alon-Tarsi number; and what can be abound for the gap between the list chromatic number and the Alon-Tarsi number? Is it arbitrarily large? Thanks beforehand.

Answer 1

Let us consider the graph $K_{n,n}$. Since the graph polynomial of $K_{n,n}$ is homogenous with degree $n^2$, we must have the Alon-Tarsi number of the graph $K_{n,n}$ to be $\ge \frac{n^2}{2n}=\frac{n}{2}$.

However, it is well known that the list chromatic number or the choice number of $K_{n,n}$ is bounded above by $\log_2n+2$. This bound is obtained by using a weighting and coloring argument: At each step, we color a certain set of vertices and double the weight on the remaining set of vertices. The procedure is repeated till long, from which the bound $\log_2n+2$ is obtained. Full proof can be found in the great book "Combinatorial Nullstellensatz" by X Zhu and R Balakrishnan here