Asymptotics of the chromatic index for multigraphs (Q1125951)

For a multigraph \(G\), let \(D(G)\) denote maximum degree and set \[ \Gamma(G)=\max\Biggl\{{|E(W)|\over \lfloor|W|/2\rfloor}: W\subseteq V, 3\leq |W|\equiv 1\pmod 2\Biggr\}. \] We show that the chromatic index \(\chi'(G)\) is asymptotically \(\max\{D(G),\Gamma(G)\}\). The latter is, by a theorem of \textit{J. Edmonds} [J. Res. Nat. Bur. Stand., Sect. B 69, 125-130 (1965; Zbl 0141.21802)], 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.