Achieving maximum chromatic index in multigraphs
by
Jessica McDonald
University of Waterloo

The chromatic index of a multigraph M, denoted by c'(M), is the minimum number of colours needed to colour the edges of M such that such that adjacent edges receive different colours. Shannon (1949), Vizing (1964) and Goldberg (1984) have all established well-known upper bounds for the chromatic index of M. In this talk we ask: when is c'(M) maximum? That is, when does c'(M) achieve a particular upper bound?

Our main result in this talk is to characterize those multigraphs which achieve Goldberg's upper bound, generalizing a 1968 result of Vizing which characterizes those muligraphs which achieve Shannon's upper bound. There is no known characterization for those multigraphs which achieve Vizing's upper bound, however we will discuss some partial results towards this, and address the issue of the complexity of this problem.

Date received: April 2, 2008

Copyright © 2008 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # cauz-11.