Fakulta matematiky, fyziky
a informatiky
Univerzita Komenského v Bratislave

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

vo štvrtok 16.12.2021 o 9:50 hod. online formou

14. 12. 2021 16.44 hod.
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.


Stránka seminára