Seminár z teórie grafov - Jonathan Narboni (26.11.2020)

vo štvrtok 26.11.2020 o 9:50 hod.


23. 11. 2020 13.20 hod.
Od: Martin Škoviera

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.

Stránka seminára