Graph coloring reconfiguration systems (Prateek Bhakta, University of Richmond)

For k >= 2, the k-coloring graph C(G) of a base graph G has a vertex set consisting of the proper k-colorings of G with edges connecting two vertices corresponding to two different colorings of G if those two colorings differ in the color assigned to a single vertex of G. A base graph whose k-coloring graph is connected is called k-mixing; here it is possible to reconfigure a particular k-coloring of G to any other k-coloring of G by changing the color of one vertex at a time in the assignment while maintaining that each intermediate step is a proper k-coloring. We explore the connectivity and biconnectivity of coloring graphs with a focus on the inverse problem: given a graph H, is H the k coloring graph of some base graph G for some k?