Vendredi 3 juin 2016 à 11h, salle 24-25/405
Abstract
Given a colouring of a graph, a Kempe change is the operation of
picking a maximal bichromatic subgraph and switching the two colours in it.
Two colourings are Kempe equivalent if they can be obtained from each other
through a series of Kempe changes. Kempe changes were first introduced in a
failed attempt to prove the Four Colour Theorem, but they proved to be a
powerful tool for other colouring problems. They are also relevant for more
applied questions, most notably in theoretical physics. Consider a graph
with no vertex of degree more than some integer D. In 2007, Mohar
conjectured that all its D-colourings are Kempe-equivalent. Feghali,
Johnson and Paulusma proved in 2015 that this is true for D=3, with the
exception of one single graph which disproves the conjecture in its
generality. We settle the remaining cases by proving the conjecture holds
for every integer D at least 4. This is a joint work with Nicolas Bousquet
(LIRIS, Ecole Centrale Lyon, France), Carl Feghali (Durham University, UK)
and Matthew Johnson (Durham University, UK).