Date: Tuesday, December 9, 2014
Location: Rockefeller Hall 310
Title: Which graphs are coloring graphs?
Abstract: For a simple graph G and a positive integer k, the k-coloring graph of G, denoted C_k(G), is the graph whose vertex set is the set of all proper (vertex) k-colorings of G with two k-colorings adjacent if they differ at exactly one vertex of G. In this talk, we consider the question: What graphs are coloring graphs? We give examples of families of graphs whose members are always, sometimes, and never coloring graphs and explore techniques useful for investigating this inverse problem.No prior knowledge of graphs is necessary. We will begin with the definition of a graph and give lots of examples along the way!