Las Vergnas–Meyniel conjecture on Kempe equivalence and graph minors

For a graph GG, a tt-colouring is a proper colouring using tt colours, and two colourings are Kempe equivalent when they are connected by a sequence of Kempe changes, each swapping two colours on a maximal bichromatic component. Let KtK_t denote the complete graph on tt vertices, and say that GG has no KtK_t-minor when it does not contain KtK_t as a graph minor. Las Vergnas–Meyniel's Conjecture A. For every tt, all the tt-colourings of a graph with no KtK_t-minor form a single equivalence class. The paper states that this conjecture is disproved by its construction of graphs with no KtK_t-minor having non-equivalent colourings.

Sources & referencesView supporting material

Primary source

Marthe Bonamy, Marc Heinrich, Clément Legrand-Duchesne and Jonathan Narboni, “On a recolouring version of Hadwiger's conjecture”, arXiv:2103.10684 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.