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.

Please contact us with feedback and comments about this page. Last updated on 03 Apr 2022 01:32.