Table of Contents
2021 Session 4 : Graph Reconfiguration
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.
Organisers
Workshop dates
31 May-4 June 2021
Confirmed participants
- 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)
Open problems
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)
Schedule
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).
Research results
- Cambie, Cames van Batenburg, Cranston. Optimally Reconfiguring List and Correspondence Colourings. https://arxiv.org/abs/2204.07928