by Marthe Bonamy
Abstract:
In his 1965 seminal paper on edge colouring, Vizing proved that a -edge colouring can be reached from any given proper edge colouring through a series of Kempe changes, where 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 -edge-colourable, can we always reach a -edge-colouring? If true, this would imply a more recent conjecture of Mohar (2006) that in any graph, all -edge-colourings are equivalent up to a series of Kempe changes. We discuss recent progress around these questions.
Event Timeslots (1)
Tuesday
-
Marthe Bonamy