Seminár z teórie grafov - Jonathan Narboni (16.12.2021)
vo štvrtok 16.12.2021 o 9:50 hod. online formou
Od: Martin Škoviera
Prednášajúci: Jonathan Narboni (LaBRI, Université de Bordeaux)
Názov: On the reconfiguration version of the Hadwiger conjecture
Termín: 16.12.2021, 9:50 hod., MS Teams
Pristupový kód do MS TEAMS je: gglxxc7
(pre účastníkov z UK v Bratislave)
The Hadwiger conjecture is one of the most famous and widely open conjecture in graph coloring. It states that a graph with no K_t-minor admits a (k-1)-coloring. In this talk we will consider a reconfiguration version of the problem. One can transform a proper coloring of a graph into another proper coloring by applying a Kempe change: ie switching the two colors of a maximal bichromatic component. Two colorings are called equivalent if there exists a sequence of Kempe changes to apply to transform the first coloring into the second.
In 1981, Las Vergnas and Meyniel conjectured a reconfiguration analog of the Hadwiger conjecture: if a graph has no K_t minor, then all its k-colorings are equivalent. We disprove this conjecture, more precisely, we prove that for any epsilon, there exists t large enough such that there exists a graph with no K_t minor, that has two ((3/2-epsilon)*t)-colorings which are not equivalent.
This is joint work with Marthe Bonamy, Clément Legrand-Duchesne, and Marc Heinrich.