# Edge Colouring Multigraphs

Thursday, November 20, 2014 - 2:00pm - 3:00pm

Lind 305

Penny Haxell (University of Waterloo)

The chromatic index of a multigraph G is the smallest k such that the edges of G can be coloured with k colours so that no two edges of the same colour share a vertex. It is easy to see that the chromatic index of G is at least the maximum degree d, and it can be as large as 3d/2.

An old conjecture due to Goldberg and (independently) Seymour essentially states that if a multigraph has chromatic index d+k > d+1 then it must contain a small odd subset S of vertices that induces too many edges to be coloured with d+k colours. This talk will report on recent joint work with Hal Kierstead proving a weakened version of this statement, and describe an important tool for studying edge colourings (the method of Tashkinov trees).

An old conjecture due to Goldberg and (independently) Seymour essentially states that if a multigraph has chromatic index d+k > d+1 then it must contain a small odd subset S of vertices that induces too many edges to be coloured with d+k colours. This talk will report on recent joint work with Hal Kierstead proving a weakened version of this statement, and describe an important tool for studying edge colourings (the method of Tashkinov trees).