Classifying coloring graphs

Given a graph GG, its kk-coloring graph is the graph whose vertex set is the proper kk-colorings of the vertices of GG with two kk-colorings adjacent if they differ at exactly one vertex. In this paper, we consider the question: Which graphs can be coloring graphs? In other words, given a graph HH, do there exist GG and kk such that HH is the kk-coloring graph of GG? We will answer this question for several classes of graphs and discuss important obstructions to being a coloring graph involving order, girth, and induced subgraphs.