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