A paintability version of the combinatorial Nullstellensatz, and list colorings of \(k\)-partite \(k\)-uniform hypergraphs (Q612968)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A paintability version of the combinatorial Nullstellensatz, and list colorings of \(k\)-partite \(k\)-uniform hypergraphs |
scientific article |
Statements
A paintability version of the combinatorial Nullstellensatz, and list colorings of \(k\)-partite \(k\)-uniform hypergraphs (English)
0 references
16 December 2010
0 references
Summary: We study the list coloring number of \(k\)-uniform \(k\)-partite hypergraphs. Answering a question of \textit{R. Ramamurthi} and \textit{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 \textit{N. Alon} and \textit{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.
0 references
list coloring number
0 references
combinatorial nullstellensatz
0 references