# 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