DIMACS Discrete Mathematics Seminar


Asymptotics of the chromatic index for multigraphs


Jeff Kahn
Rutgers University


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


4:30 PM
Tuesday, March 7, 1995


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