Reconfiguring List Colorings

Tuesday, March 7, 2023 - 3:45pm for 1 hour (actually 50 minutes)
Skiles 005
Daniel Cranston – Virginia Commonwealth University – dcranston@vcu.edu
Tom Kelly

A \emph{list assignment} $L$ gives to each vertex $v$ in a graph $G$ a
list $L(v)$ of
allowable colors.  An \emph{$L$-coloring} is a proper coloring $\varphi$ such that
$\varphi(v)\in L(v)$ for all $v\in V(G)$.  An \emph{$L$-recoloring move} transforms
one $L$-coloring to another by changing the color of a single vertex.  An
\emph{$L$-recoloring sequence} is a sequence of $L$-recoloring moves.  We study
the problem of which hypotheses on $G$ and $L$ imply that for that every pair
$\varphi_1$ and $\varphi_2$ of $L$-colorings of $G$ there exists an $L$-recoloring
sequence that transforms $\varphi_1$ into $\varphi_2$.  Further, we study bounds on
the length of a shortest such $L$-recoloring sequence.

We will begin with a survey of recoloring and list recoloring problems (no prior
background is assumed) and end with some recent results and compelling
conjectures.  This is joint work with Stijn Cambie and Wouter Cames van