Ottawa–Carleton
Discrete Mathematics Group

7 November 2008, 11.30am
HP4351, Carleton

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 well-known 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 Seymour-Goldberg Conjecture in the context of this problem, and demonstrate a powerful structural technique for edge-colouring: the method of Tashkinov trees. Our main result is a partial characterization of Vizing's upper bound for multiples of simple graphs.