Asymptotics of the chromatic index for multigraphs (Q1125951)

From MaRDI portal





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
    0 references
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references