Seminar of Graph Theory - Jonathan Narboni (16.12.2021)
Thursday 16.12.2021 at 9:50, online
By: Martin Škoviera
Jonathan Narboni (LaBRI, Université de Bordeaux):
On the reconfiguration version of the Hadwiger conjecture
Access code for MS TEAMS je: gglxxc7
(Access code for Comenius University only)
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.