Title: Connectivity in graph coloring reconfiguration

Abstract: A reconfiguration system consists of a collection of states and a rule for transitioning between states. This can be represented via a graph where states are vertices and transitions are edges. From this perspective, one can use graph theoretic tools to study the structure and algorithmic properties of a reconfiguration system. In this talk, we consider the reconfiguration system which has a set of states consisting of the proper vertex k-colorings of a fixed underlying graph and a transition rule given by recoloring a single vertex of that graph. We will focus on connectivity properties of these systems including their block-cut structure giving many examples along the way. This is joint work with Prateek Bhakta (UR), Sara Krehbiel (Santa Clara U), Howard Levinson (Santa Clara U), and many of our current and former undergraduate students.

 

Colloquium Seminars are held on select Fridays throughout the year. These broad audience presentations are intended to introduce the VCU community to the world of mathematics. Colloquium presentations explore topics in mathematics, applied mathematics, math history and education, and the exciting connections between math, science, art and humanities.