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: 

Please contact one of the organizers for Zoom connection details:

Kevin Halasz

Alexandra Wesolek 

Danielle Rogers