SFU Discrete Math Seminar: Marthe Bonamy (Online)
Topic
On Vizing's edge colouring question
Speakers
Details
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.
Additional Information
Please contact one of the organizers for Zoom connection details:
Marthe Bonamy, LaBRI
This is a Past Event
Event Type
Scientific, Seminar
Date
September 17, 2020
Time
-
Location