[gt.go] - "Recoloring planar graphs with Kempe changes" by Clément Legrand-Duchesne
/Exposé en anglais/Talk in english/
Given a coloring of a fixed graph G, a Kempe chain is a maximal bichromatic connected component. A Kempe change is a recoloring operation consisting in swapping the two colors inside a Kempe chain. Meyniel proved in 1978 that any two 5-colorings of a planar graph are equivalent up to a series of O(5|V(G)|) Kempe changes. We strengthen this result, by proving that any two 5-colorings of a planar graph are equivalent up to a polynomial number of Kempe changes.
This is a first step towards bounding polynomially the diameter of the reconfiguration graph of d-degenerate graphs.
[Clément Legrand-Duchesne] (LaBRI )
Remarks / Remarques
Find all the information of the working group on this [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT?userlang=en | web page ] .
Retrouvez toutes les informations du GT sur cette [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT | page web ] .