Ruth Haas (Smith College): Reconfiguration in Graph Coloring

When:
July 5, 2016 @ 3:30 pm – 4:20 pm
2016-07-05T15:30:00-10:00
2016-07-05T16:20:00-10:00
Where:
Keller Hall 401

Reconfiguration in Graph Coloring

In mathematics, as in life, there are often multiple solutions to a question.
Reconfiguration studies whether it is possible to move from one solution to
another following a given set of rules. Is it possible? How long will it take?
In this talk, we will consider reconfiguration of graph coloring.

A proper coloring of a graph is an assignment of a color to each vertex of the
graph so that neighboring vertices have different colors. 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 yes, if we are allowed an unlimited number of
colors. But, what is the fewest colors we can have for this to work? How many
steps might it take? We will look at this, related questions and generalizations.