W&M Featured Events
[PAST EVENT] Mathematics Colloquium - Dan Cranston (VCU)
Access & Features
- Free food
- Open to the public
Reconfiguration of Colorings and List Colorings
A \emph{proper $k$-coloring} of a graph $G$ assigns to each vertex $v$ a color $\alpha(v)$, with $\alpha(v)\in {1,\ldots,k}$ such that $\alpha(v) \ne \alpha(w)$ for every edge $vw$. (A \emph{list coloring} is similar, except that distinct vertices may have distinct lists of allowable colors.)
A \emph{recoloring step} in a graph $G$ for a coloring $\alpha$ recolors some vertex $v$ with a color allowable for $v$ that is not used by $\alpha$ on any neighbor of $v$, yielding a new proper coloring. Given proper colorings $\alpha$ and $\beta$ of $G$, we ask questions like: Can we transform $\alpha$ to $\beta$ by a sequence of recoloring steps? And: Over all $\alpha$ and $\beta$, what is the longest that a shortest sequence from $\alpha$ to $\beta$ can be?
In this talk we survey results on reconfiguration of colorings and list colorings. We end with a few conjectures.
Refreshments in lobby of Jones Hall at 1:30pm
Sponsored by: Mathematics
Contact
Gexin Yu