Noon lecture

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

On 17.01.2019 at 12:30 in S10, there is the following noon lecture:

Paths between colourings of sparse graphs

Carl Feghali

University of Bergen

Abstract

The reconfiguration graph R_k(G) of the k-colourings of a graph G has as vertex set the k-colourings of G and two vertices of R_k(G) are joined by an edge if the corresponding colourings differ on the colour of exactly one vertex. Given a k-degenerate graph G, a conjecture of Cereceda from 2008 states that R_{k+2}(G) has diameter O(|V(G)|^2). I will give a short proof of an existing theorem that addresses the conjecture for graphs with bounded maximum average degree. I will also discuss some progress on the conjecture for planar graphs.

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

Webmaster: kamweb.mff.cuni.cz         Modified: 25. 02. 2019