Faculty of Mathematics, Physics
and Informatics
Comenius University Bratislava

Seminar of Graph Theory - Jonathan Narboni (16.12.2021)

Thursday 16.12.2021 at 9:50, online

14. 12. 2021 16.51 hod.
By: Martin Škoviera

Jonathan Narboni (LaBRI, Université de Bordeaux):
On the reconfiguration version of the Hadwiger conjecture

MS Teams 

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.

More information