IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

Classifying Coloring Graphs

  • Oct. 7, 2013
  • 3:15 p.m.
  • LeConte 312


If G is a simple graph, then the k-coloring graph of G is the graph whose vertex set is the set of all proper k-colorings of G, with two k-colorings adjacent when they differ in color on exactly one vertex of G. In this talk we will attempt to answer the question: what graphs can be coloring graphs? We will establish several lemmas that will help us classify all coloring graphs of certain orders, including all those of order less than 20, of prime order, and all those with k=2. We will see that the 5-cycle, C_5, cannot be an induced subgraph of any coloring graph, but that all other cycles can be. We will also show that trees cannot be coloring graphs and that, with a few exceptions, neither can cycles. A few more potentially useful lemmas will be presented, along with some open questions.

© Interdisciplinary Mathematics Institute | The University of South Carolina Board of Trustees | Webmaster