Noon lecture

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

On 08.12.2016 at 12:20 in S6, there is the following noon lecture:

Kempe equivalence of colourings

Marthe Bonamy

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. Since 1981, we know from Las Vergnas and Meyniel that this is true if the graph is not D-regular. Feghali, Johnson and Paulusma proved in 2015 that 3-regular graphs also satisfy the conjecture, with the exception of the 3-prism (two triangles joined by a matching) which disproves it. We settle the remaining cases by proving that all k-colourings of a k-regular graph are Kempe equivalent for k at least 4.

This is a joint work with Nicolas Bousquet (CNRS, G-SCOP, France), Carl Feghali (IRIF, France) and Matthew Johnson (Durham University, UK).

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

Webmaster: kamweb.mff.cuni.cz         Modified: 19. 10. 2010