14:00
15:00

[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 )

[ https://www.labri.fr/perso/clemlegrand/ | https://www.labri.fr/perso/clemlegrand/ ]

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 ] .

https://webconf.u-bordeaux.fr/b/mar-ef4-zed and LaBRI/178