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

Abstract

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 Nullstellensatz.