A Paintability Version of the Combinatorial Nullstellensatz, and List Colorings of k-partite k-uniform Hypergraphs

We study the list coloring number of k-uniform k-partite hypergraphs. Answering a question of Ramamurthi and West, we present a new upper bound which generalizes Alon and Tarsi's bound for bipartite graphs, the case k = 2. Our results hold even for paintability (on-line list colorability). To prove this additional strengthening, we provide a new subject-specific version of the Combinatorial Null-stellensatz.