# Noon lecture

On 17.1.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.

Webmaster: kamweb.mff.cuni.cz Archive page