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 to 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.

Marthe Bonamy and Nicolas Bousquet

31 May-4 June 2021

• Marthe Bonamy (organiser)
• Nicolas Bousquet (organiser)
• Valentin Bartier
• Sébastien Bonduelle
• Marcin Brianski
• Stijn Cambie
• Wouter Cames van Batenburg
• Dan Cranston
• Matt Coulson
• Konrad Dabrowski
• Carl Feghali
• Laurent Feuilloley
• Aliénor Goubault
• Marc Heinrich
• Felix Hommelsheim
• Clément Legrand-Duchesne
• Frantisek Kardos
• Tomas Kaiser
• Aurelie Lagoutte
• Owen Merkel
• Benjamin Moore
• Amer Mouawad
• Moritz Muhlenthaler
• Jonathan Narboni
• Guillem Perarnau
• Sebastian Siebertz

Registration details: Please send an email to the organizers if you are interested to participate.

Registration deadline: 21st of May (closed)

Submission details: Template: https://www.mimuw.edu.pl/~mp248287/opl-example.tgz

Submit open problems related to reconfiguration (generously interpreted) by email to the organisers. The main aim of the workshop is to work on and solve these!

Submission deadline: 27th of May (closed)

1. Monday, 31 May
  9h45 - Introduction
  10h - Amer Mouawad - Algorithmic aspects of reconfiguration
  11h15 - Marc Heinrich - A survey on graph recoloring
  14h - Open problem session
  15h30 - Partition into small groups
2. Tuesday, 1 June
  11h - Coffee break (on Wonder)
  15h - Cofee break (on Wonder)
  15h30 - Progress report
3. Wednesday, 2 June
  11h - Coffee break (on Wonder)
  15h - Cofee break (on Wonder)
  15h30 - Progress report
4. Thursday, 3 June
  11h - Coffee break (on Wonder)
  15h - Cofee break (on Wonder)
  15h30 - Progress report
5. Friday, 4 June
  11h - Coffee break (on Wonder)
  14h30 - Progress report

(All the time have to be read Central European Summer Time, i.e. UTC+2).

• Cambie, Cames van Batenburg, Cranston. Optimally Reconfiguring List and Correspondence Colourings. https://arxiv.org/abs/2204.07928