Discrete Mathematics and Combinatorics Commons^™

Classifying Coloring Graphs, Julie Beier, Janet Fierson, Ruth Haas, Heather M. Russell, Kara Shavo

Department of Math & Statistics Faculty Publications

Given a graph G, its k-coloring graph is the graph whose vertex set is the proper k-colorings of the vertices of G with two k-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 H, do there exist G and k such that H is the k-coloring graph of G? 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.