Seminar of Graph Theory - Jonathan Narboni (26.11.2020)
Thursday 26.11.2020 at 9:50
By: Martin Škoviera
Jonathan Narboni (LABRI University of Bordeaux):
On Vizing's edge coloring question
MS TEAMS code (users from Comenius University in Bratislava): gglxxc7
Link (guests outside Comenius University in Bratislava)
In his 1965 seminal paper on edge coloring, Vizing proved that a (Delta+1)-edge coloring can be reached from any given proper edge coloring 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 coloring be reached from any given proper edge coloring through a series of Kempe changes? In other words, if the graph is Delta-edge-colorable, can we always reach a Delta-edge-coloring? We discuss a key ingredient in Vizing's original paper, namely the use of fans; we show how to extend the notion and answer his question in the affirmative for all triangle-free graphs.
This is a joint work with M. Bonamy, O. Defrain, T. Klimosova, and A. Lagoutte.