# 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.

dimacs-www@dimacs.rutgers.edu
Document last modified on February 27, 1995