Date
Tue, 01 Feb 2022
14:00
Location
Virtual
Speaker
Clément Legrand-Duchesne
Organisation
LaBRI Bordeaux

Las Vergnas and Meyniel conjectured in 1981 that all the $t$-colorings of a $K_t$-minor free graph are Kempe equivalent. This conjecture can be seen as a reconfiguration counterpoint to Hadwiger's conjecture, although it neither implies it or is implied by it. We prove that for all positive $\epsilon$, for all large enough $t$, there exists a graph with no $K_{(2/3 + \epsilon)t}$ minor whose $t$-colorings are not all Kempe equivalent, thereby strongly disproving this conjecture, along with two other conjectures of the same paper.

Last updated on 3 Apr 2022, 1:32am. Please contact us with feedback and comments about this page.