
Discrete Mathematics and Optimization Seminar

Oct. 29, 2008
MC 320, 4:30 PM
Multigraphs With High Chromatic Index: Vizing's Bound
Jessica McDonald
Waterloo

The chromatic index of a multigraph G is the minimum number of colours needed to colour the edges of G such that adjacent edges receive different colours. There are a number of wellknown upper bounds on chromatic index, due to Shannon (1949), Vizing (1964) and Goldberg (1984). But which multigraphs actually achieve these upper bounds?
In this talk we study multigraphs with high chromatic index, with a particular focus on those multigraphs achieving Vizing's upper bound. We discuss the significance of the SeymourGoldberg Conjecture in the context of this problem, and demonstrate a powerful structural technique for edgecolouring: the method of Tashkinov trees. Our main result is a partial characterization of Vizing's upper bound for multiples of simple graphs.



