|
|||||
 |
|
|
|
|
|
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 , its -coloring graph has vertex set given by the proper -colorings of the vertices of with two -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
|
Mathematical Subject Classification 2010
Primary: 05C15
|
Milestones
Received: 10 November 2016
Revised: 14 May 2017
Accepted: 19 June 2017
Published: 17 September 2017
Communicated by Jerrold Griggs
|
Authors |
| Francisco Alvarado | |
| California State University Los Angeles, CA United States |
|
| Ashley Butts | |
| University of the Pacific Stockton, CA United States |
|
| Lauren Farquhar | |
| Department of Mathematics University of Colorado Boulder, CO United States |
|
| Heather M. Russell | |
| Department of Mathematics University of Richmond Richmond, VA United States |
|
|
