Asymptotics of the chromatic index for multigraphs (Q1125951)
From MaRDI portal
![]() | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Asymptotics of the chromatic index for multigraphs |
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Asymptotics of the chromatic index for multigraphs |
scientific article |
Statements
Asymptotics of the chromatic index for multigraphs (English)
0 references
19 May 1997
0 references
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.
0 references
matching polytope
0 references
hard-core distributions
0 references
incremental -random method
0 references
multigraph
0 references
maximum degree
0 references
chromatic index
0 references
fractional chromatic index
0 references
hypergraphs
0 references
colorings
0 references