Sparse Graphs Coalition

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
===== 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 ====

[[https://www.labri.fr/perso/mbonamy/|Marthe Bonamy]] and [[https://perso.liris.cnrs.fr/nbousquet/|Nicolas Bousquet]]

==== Workshop dates ====

31 May-4 June 2021

==== Confirmed participants ====

  * [[marthe.bonamy@u-bordeaux.com|Marthe Bonamy]] (organiser)
  * [[nicolas.bousquet@univ-lyon1.fr|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