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). Department of Math & Statistics Faculty Publications. 169.
https://scholarship.richmond.edu/mathcs-faculty-publications/169