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.

05C65 Hypergraphs
05C15 Coloring of graphs and hypergraphs
Full Text: DOI