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.

Document Type

Post-print Article

Publication Date


Publisher Statement

Copyright © 2016 Elsevier B.V.

DOI: 10.1016/j.disc.2016.03.003

The definitive version is available at:

Full Citation:

Beier, Julie, Janet Fierson, Ruth Haas, Heather M. Russell, and Kara Shavo. "Classifying Coloring Graphs." Discrete Mathematics 339, no. 8 (2016): 2100-2112. doi:10.1016/j.disc.2016.03.003.