List coloring hypergraphs (Q1960283)

Summary: Let \(H\) be a hypergraph and let \(L_v: v\in V(H)\) be sets; we refer to these sets as lists and their elements as colors. A list coloring of \(H\) is an assignment of a color from \(L_v\) to each \(v\in V(H)\) in such a way that every edge of \(H\) contains a pair of vertices of different colors. The hypergraph \(H\) is \(k\)-list-colorable if it has a list coloring from any collection of lists of size \(k\). The list chromatic number of \(H\) is the minimum \(k\) such that \(H\) is \(k\)-list-colorable. In this paper we prove that every \(d\)-regular three-uniform linear hypergraph has list chromatic number at least \(\left(\frac{\log d}{5\log\log d}\right)^{1/2}\) provided \(d\) is large enough. On the other hand there exist \(d\)-regular three-uniform linear hypergraphs with list chromatic number at most \(\log_3 d + 3\). This leaves the question open as to the existence of such hypergraphs with list chromatic number \(o(\log d)\) as \(d\to\infty\).