Las Vergnas–Meyniel conjecture on Kempe equivalence and graph minors
Las Vergnas–Meyniel conjecture on Kempe equivalence and graph minors
For a graph , a -colouring is a proper colouring using 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 denote the complete graph on vertices, and say that has no -minor when it does not contain as a graph minor. Las Vergnas–Meyniel's Conjecture A. For every , all the -colourings of a graph with no -minor form a single equivalence class. The paper states that this conjecture is disproved by its construction of graphs with no -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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.