#### DOI

10.1016/j.disc.2016.03.003

#### Abstract

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

2016

#### Publisher Statement

Copyright © 2016 Elsevier B.V.

DOI: 10.1016/j.disc.2016.03.003

The definitive version is available at: http://www.sciencedirect.com/science/article/pii/S0012365X16300401?np=y&npKey=d6631d9bd87251c39b9473072152ef5dd40c1415dc546f5387178578f27687db

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.

#### Recommended Citation

Beier, Julie; Fierson, Janet; Haas, Ruth; Russell, Heather M.; and Shavo, Kara, "Classifying Coloring Graphs" (2016). *Math and Computer Science Faculty Publications*. 169.

https://scholarship.richmond.edu/mathcs-faculty-publications/169