## SFU Discrete Math Seminar: Marthe Bonamy (Online)

• Date: 09/16/2020
• Time: 10:30
Lecturer(s):
Marthe Bonamy, LaBRI
Location:

Online

Topic:

On Vizing's edge colouring question

Description:

In his 1965 seminal paper on edge colouring, Vizing proved that a (Delta+1)-edge colouring can be reached from any given proper edge colouring through a series of Kempe changes, where Delta is the maximum degree of the graph. He concludes the paper with the following question: can an optimal edge colouring be reached from any given proper edge colouring through a series of Kempe changes? In other words, if the graph is Delta-edge-colourable, can we always reach a Delta-edge-colouring? If true, this would imply a more recent conjecture of Mohar (2006) that in any graph, all (Delta+2)-edge-colourings are equivalent up to a series of Kempe changes. We discuss recent progress around these questions.

Other Information: