Seminár z teórie grafov - Jonathan Narboni (26.11.2020)
vo štvrtok 26.11.2020 o 9:50 hod.
Prednášajúci: Jonathan Narboni (LABRI University of Bordeaux)
Názov: On Vizing's edge coloring question
Termín: 26.11.2020, 9:50 hod.
Prístupový kód do MS TEAMS (pre používateľov z UK): gglxxc7
Pripojenie (pre hostí mimo UK)
Abstrakt:
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.