#### Vol. 11, No. 2, 2018

 Recent Issues
 The Journal About the Journal Subscriptions Editorial Board Editors’ Interests Scientific Advantages Submission Guidelines Submission Form Ethics Statement Editorial Login Author Index Coming Soon Contacts ISSN: 1944-4184 (e-only) ISSN: 1944-4176 (print)
Forbidden subgraphs of coloring graphs

### Francisco Alvarado, Ashley Butts, Lauren Farquhar and Heather M. Russell

Vol. 11 (2018), No. 2, 311–324
##### Abstract

Given a graph $G$, its $k$-coloring graph has vertex set given by the proper $k$-colorings of the vertices of $G$ with two $k$-colorings adjacent if and only if they differ at exactly one vertex. Beier et al. (Discrete Math. 339:8 (2016), 2100–2112) give various characterizations of coloring graphs, including finding graphs which never arise as induced subgraphs of coloring graphs. These are called forbidden subgraphs, and if no proper subgraph of a forbidden subgraph is forbidden, it is called minimal forbidden. In this paper, we construct a finite collection of minimal forbidden subgraphs that come from modifying theta graphs. We also construct an infinite family of minimal forbidden subgraphs similar to the infinite family found by Beier et al.

##### Keywords
proper graph coloring, coloring graph, forbidden subgraph
Primary: 05C15