On a recolouring version of Hadwiger's conjecture
We prove that for any ε>0, for any large enough t, there is a graph G that admits no K_t-minor but admits a (3/2-ε)t-colouring that is "frozen" with respect to Kempe changes, i.e. any two colour classes induce a connected component. This disproves three conjectures of Las Vergnas and Meyniel from 1981.
READ FULL TEXT