Combinatorics Seminar

When: Sunday, April 10, 10am

Where: Schreiber 309

Speaker: Penny Haxell, University of Waterloo

Title: Edge Colouring Multigraphs

Abstract:

Vizing's classical theorem tells us that there are only two possible values for the edge chromatic number of a graph $G$, namely $\Delta(G)$ and $\Delta(G)+1$, where $\Delta(G)$ denotes the maximum degree of $G$. However, for multigraphs the situation is more complicated and much less well understood. We discuss some old open problems and some relatively recent partial results related to edge colouring. One of the principal tools is an important method due to Tashkinov, called the method of Tashkinov trees, which is a sophisticated generalization of the method of alternating paths.

w3c valid   accessible website
redesigned by barak soreq