Kahn, Jeff Asymptotically good list-colorings. (English) Zbl 0851.05081 J. Comb. Theory, Ser. A 73, No. 1, 1-59 (1996). Summary: The list-chromatic index, \(\chi_l'({\mathcal H})\), of a hypergraph \(\mathcal H\) is the least \(t\) such that for any assignment of \(t\)-sets \(S(A)\) to the edges \(A\) of \(\mathcal H\), there is a proper coloring \(\sigma\) of \(\mathcal H\) with \(\sigma(A)\in S(A)\) for all \(A\in {\mathcal H}\). Theorem: Let \(k\) be fixed and \(\mathcal H\) a hypergraph having edges of size at most \(k\) and maximum degree \(D\), and satisfying \(\max\{d(x, y)\mid x, y\) distinct vertices of \({\mathcal H}\}= o(D)\). Then \(\chi_l'({\mathcal H})/D\to 1\) \((D\to \infty)\).Thus if edge sizes are bounded and pairwise degrees are relatively small, we have asymptotic agreement of \(\chi_l'\) with its trivial lower bound, the maximum degree. The corresponding result for ordinary chromatic index is a theorem of N. Pippenger and J. Spencer [J. Comb. Theory, Ser. A 51, No. 2, 24-42 (1989; Zbl 0729.05038)]. On the other hand, even for simple graphs, earlier work falls far short of deciding the asymptotic behavior of \(\chi_l'\). The “guided-random” method used in the prof is in the spirit of some ealier work and is thought to be of particular interest. One simple ingredient is a martingale inequality which ought to prove useful beyond the present context. Cited in 2 ReviewsCited in 48 Documents MSC: 05C65 Hypergraphs 05C15 Coloring of graphs and hypergraphs Keywords:list-chromatic index; hypergraph Citations:Zbl 0729.05038 PDFBibTeX XMLCite \textit{J. Kahn}, J. Comb. Theory, Ser. A 73, No. 1, 1--59 (1996; Zbl 0851.05081) Full Text: DOI