ASYMPTOTICS OF THE CHROMATIC INDEX FOR MULTIGRAPHS

摘要

For a multigraph G, let D(G) denote maximum degree and set Gamma(G) = max {E(W)/[W/2] : W subset of or equal to V, 3 less than or equal to W = 1 (mod 2)}. We show that the chromatic index chi'(G) is asymptotically mart {D(G), Gamma(G)}. The latter is, by a theorem of Edmonds (1965), the fractional chromatic index of G, and the asymptotics established here are part of a conjecture of the author predicting similar agreement of fractional and ordinary chromatic indices for more general hypergraphs. OF particular interest in the present proof is the use of probabilistic ideas and ''hard-core'' distributions to go From fractional to ordinary (integer)colorings. (C) 1996 Academic Press, Inc. [References: 62]