Asymptotics of the list-chromatic index for multigraphs

The list-chromatic index, chi(1)(')(G) of a multigraph G is the least t suc h that if S(A) is a set of size t for each A epsilon E := E(G), then there exists a proper coloring sigma of G with sigma(A) epsilon S(A) fur each A e psilon E. The list-chromatic index is bounded below by the ordinary chromat ic index, chi'(G), which in turn is at least the fractional chromatic index , chi'*(G) In previous work we showed that the chromatic and fractional chr omatic indices are asymptotically the same; here we extend this to the list -chromatic index: chi(1)(')(G) similar to chi'*(G) as chi(1)(')(G) --> infi nity. The proof uses sampling from "hard-core" distributions on the set of matchings of a multigraph to go from fractional to list colorings. (C) 2000 John Wiley & Sons, Inc.