zbMATH — the first resource for mathematics

A paintability version of the combinatorial Nullstellensatz, and list colorings of \(k\)-partite \(k\)-uniform hypergraphs. (English) Zbl 1201.05039
Summary: We study the list coloring number of \(k\)-uniform \(k\)-partite hypergraphs. Answering a question of R. Ramamurthi and D.B. West [“Hypergraph extension of the Alon-Tarsi list coloring theorem,” Combinatorica 25, No. 3, 355–366 (2005; Zbl 1080.05034)], we present a new upper bound which generalizes N. Alon and M. Tarsi’s bound for bipartite graphs [“Colorings and orientations of graphs,” Combinatorica 12, No. 2, 125–134 (1992; Zbl 0756.05049)], 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.

05C15 Coloring of graphs and hypergraphs
11C08 Polynomials in number theory
91A43 Games involving graphs
05C65 Hypergraphs
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
Full Text: EMIS EuDML arXiv