Asymptotics of the Chromatic Index for Multigraphs
详细信息 查看全文
文摘
For a multigraphG, letD(G) denote maximum degree and set[formula]We show that the chromatic indexχ′(G) is asymptotically max{D(G),Ggr;(G)}. The latter is, by a theorem of Edmonds (1965), the fractional chromatic index ofG, 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.