Sparse Graphs Coalition

In graph reconfiguration, we are given two solutions of a problem and the goal is to transform a solution into another while keeping a valid solution all along the transformation. Reconfiguration is related to various fields such as enumeration, counting, random sampling, discrete geometry, bio-informatics, or combinatorial game theory.

The goal of the workshop is to tackle combinatorial and algorithmic questions related to graph reconfiguration in general with a special attention in graph recoloring. Graph recoloring has been studied for more than 40 years with two possible recoloring steps: single vertex recolorings (at each step we can change the color of one vertex) and Kempe recolorings (where at each step we can flip the colors of a Kempe chain). In particular, one can ask the following question: you many colors are needed to guarantee that we can transform any k-coloring into any other by allowing to recolor only one vertex at a time? For planar graphs, for instance, one can easily show that the answer is 7. If such a transformation exists, how many steps are needed? In the case of planar graphs, the answer to this question is still open.

This workshop will focus mainly on exploring the connections with other areas.

31 May-4 June 2021

• Marthe Bonamy (organiser)
• Nicolas Bousquet (organiser)

Registration details: tba

Registration deadline: tba

Submission details: tba

Submission deadline: tba

1. Monday, 31 May
  a. 
2. Tuesday, 1 June
  a. 
3. Wednesday, 2 June
  a. 
4. Thursday, 3 June
  a. 
5. Friday, 4 June
  a.