Alon-Tarsi Number

The Alon-Tarsi number of a graph is the least positive integer such that the graph polynomial of contains a monomial with nonzero coefficient in which every variable has exponent less than . To write the definition explicitly, label the vertices of by , ..., , choose a graph orientation of its edges, and form

(1)

If

(2)

then equivalently

(3)

It is independent of the chosen graph orientation and is an upper bound for the list chromatic number of by the combinatorial nullstellensatz (Alon and Tarsi 1992).

More generally, the same formula defines the Alon-Tarsi number of a polynomial. For a hypergraph , a hypergraph polynomial has the form

(4)

where every coefficient is nonzero. Anholcer et al. (2026) prove that the fully balanced polynomial over a field of field characteristic zero has Alon-Tarsi number , where

(5)

is the edge density. For a fully unbalanced hypergraph polynomial, its coefficients can be permuted within the hyperedges so that the resulting Alon-Tarsi number is at most .