Mathematics Colloquium: Reconfiguration in graph coloring and graph domination

School of Mathematical Sciences Colloquium
Reconfiguration in graph coloring and graph domination

Dr. Ruth Haas
Professor and Graduate Chair
Department of Mathematics
University of Hawaii at Manoa

You may attend this lecture in person at 2305 Gosnell Hall or virtually via Zoom.
If you’d like to attend virtually, you may register here for Zoom link.

Abstract:
In mathematics, as in life, there are often multiple solutions to a question. Reconfiguration studies the relationship between various solutions to a problem. In particular, is it possible to move from one solution to another following a given set of rules. In this talk, we will consider reconfiguration of graph coloring and graph domination.
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. The standard reconfiguration rule is to change the color of just one vertex at a time. What conditions allow us to get from one coloring to another by a sequence of vertex changes with the condition that each step along the way is a proper coloring? We give some motivating applications and some results.
In a graph with vertex set V, a dominating set is a subset S of vertices such that every vertex in V is either in S or adjacent to a vertex in S. We consider reconfiguring dominating sets by adding and subtracting vertices from a set and describe some recent results.

Speaker Bio:
Ruth Haas is an American mathematician and professor at the University of Hawaii at Manoa. Previously she was the Achilles Professor of Mathematics at Smith College. She received the M. Gweneth Humphreys Award from the Association for Women in Mathematics (AWM) in 2015 for her mentorship of women in mathematics. Haas was named an inaugural AWM Fellow in 2017. In 2017 she was elected President of the AWM and on February 1, 2019 she assumed that position. Her research is in combinatorics and includes graph theory as well as algebraic combinatorics.

Intended Audience:
Undergraduates, graduates, and experts. Those with interest in the topic.

Find out more about upcoming speakers on the SMS Colloquium webpage.
To request an interpreter, please visit myaccess.rit.edu