Asymptotics of the chromatic index for multigraphs
type: Item
instance of: scholarly article
title: Asymptotics of the chromatic index for multigraphs
zbMATH Open document ID: 0861.05026
published in: Journal of Combinatorial Theory. Series B
publication date: 1997-05-19T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 954826
zbMATH Keywords: matching polytope
zbMATH Keywords: hard-core distributions
zbMATH Keywords: incremental -random method
zbMATH Keywords: multigraph
zbMATH Keywords: maximum degree
zbMATH Keywords: chromatic index
zbMATH Keywords: fractional chromatic index
zbMATH Keywords: hypergraphs
zbMATH Keywords: colorings
author: J. Kahn
reviewed by: Peter J. Kahn
MaRDI profile type: Publication
full work available at URL: jctb.1996.0067
OpenAlex ID: W2044004462
DOI: 10.1006/JCTB.1996.0067
description: scientific article; zbMATH DE number 954826