Mathematics Program Presents
The Coloring Graph and Variations
Thursday, October 18, 2012
RKC 111
A lecture by
Ruth Haas
Smith College
Ruth Haas
Smith College
A proper coloring is an assignment of a color to each vertex of a graph G so that neighboring vertices have different colors. Graph coloring has been a motivating topic for much of graph theory.
Suppose we change the color of just one vertex in a graph coloring. Can we get from one coloring to another by a sequence of vertex changes so that each step along the way is a proper coloring? The answer is of course yes, if we are allowed an unlimited number of colors. What is the fewest colors we can have for this to work?
We introduce a new graph called the coloring graph to analyze this situation. The coloring graph, and similar constructions, can be used to solve problems ranging from counting the possible number of graph colorings to modeling spin configurations in atoms.
For more information, call 845-758-7362, or e-mail [email protected].
Location: RKC 111