DIMACS Discrete Mathematics Seminar


Title:

Asymptotics of the chromatic index for multigraphs

Speaker:

Jeff Kahn
Rutgers University

Place:

Seminar Room 431, CoRE Building,
Busch Campus, Rutgers University

Time:

4:30 PM
Tuesday, March 7, 1995

Abstract:

For a multigraph $G$, let $D(G)$ denote maximum degree and set

$$ \Gamma(G)= \max\{\frac{|E(W)|}{\lfloor |W|/2\rfloor}: W\subseteq V, 3\leq |W|\equiv 1\pmod{2}\}, $$

where $E(W)$ is the set of edges having both ends in $W$. We show that the chromatic index $\chi'(G)$ is asymptotically $\max\{D(G),\Gamma(G)\}$. The latter is, by Edmonds' Matching Polytope Theorem, the fractional chromatic index of $G$. The proof uses a probabilistic approach, based on entropy-maximizing (also called ``normal'') distributions on matchings, to go from fractional to ordinary (integer) colorings.


Document last modified on February 27, 1995