# zbMATH — the first resource for mathematics

Asymptotically good list-colorings. (English) Zbl 0851.05081
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.

##### MSC:
 05C65 Hypergraphs 05C15 Coloring of graphs and hypergraphs
##### Keywords:
list-chromatic index; hypergraph
Full Text: