On a recolouring version of Hadwiger's conjecture

03/19/2021
by   Marthe Bonamy, et al.
0

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

Please sign up or login with your details

Forgot password? Click here to reset