On May 23, 2022, Stijn Cambie from the IBS Extremal Combinatorics and Probability Group gave a talk at the Discrete Math Seminar on the problem of determining the diameter of the reconfiguration graphs arising from the list coloring and the DP-coloring of graphs. The title of his talk was “The precise diameter of reconfiguration graphs“.
Reconfiguration is about changing instances in small steps. For example, one can perform certain moves on a Rubik’s cube, each of them changing its configuration a bit. In this case, in at most 20 steps, one can end up with the preferred result. One could construct a graph with as nodes the possible configurations of the Rubik’s cube (up to some isomorphism) and connect two nodes if one can be obtained by applying only one move to the other. Finding an optimal solution, i.e. a minimum number of moves to solve a Rubik’s cube is now equivalent to finding the distance in the graph.
We will wonder about similar problems in reconfiguration, but applied to list- and DP-colouring. In this case, the small step consists of recolouring precisely one vertex. Now we will be interested in the diameter of the reconfiguration graph and show that sometimes we can determine the precise diameters of these.
As such, during this talk, we present some main ideas of [arXiv:2204.07928].
The IBS Discrete Mathematics Group welcomes Dr. Stijn Cambie, a new (and first) research fellow at the IBS Extremal Combinatorics and Probability Group from May 16, 2022. He received his Ph.D. from the Radboud University in the Netherlands under the supervision of Prof. Ross Kang. He is interested in extremal problems on various graph parameters and in extremal set theory.