Mathematics Program Presents
Thursday, October 18, 2012
The Coloring Graph and Variations
A lecture by
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 conﬁgurations in atoms.
For more information, call 845-758-7362, or e-mail email@example.com.
Location: RKC 111