Bilkent University
Department of Computer Engineering
SEMINAR
Coloring Reconfiguration
Asst.Prof.Reem Mahmoud
Division of Science
NYU Abu Dhabi
Abstract: Reconfiguration is the concept of moving between different states of a system by transforming one state into another using some prescribed transformation rule. Reconfiguration problems are often modeled using graphs. For a given reconfiguration problem, we define a reconfiguration graph, which reformulates the problem in the language of graph theory. Each vertex of the reconfiguration graph represents a valid state of the system, and two vertices are adjacent when one corresponding state is reconfigurable to the other by a single reconfiguration step (i.e. a single application of the transformation rule). An (alpha,beta)-Kempe swap in a properly colored graph interchanges the colors on some component of the subgraph induced by colors alpha and beta. Two k-colorings of a graph are k- equivalent if we can form one from the other by a sequence of Kempe swaps. We introduce the k-coloring reconfiguration problem, which asks whether two given k-colorings of a graph are k-equivalent, and discuss extensions to its variant, the list-coloring reconfiguration problem, along with our contribution(s) towards it.
Brief Bio: Reem Mahmoud is a Visiting Assistant Professor of Computer Science at NYU Abu Dhabi. She earned her PhD in Computer Science from Virginia Commonwealth University, where she also earned her MSc in Mathematics. She also holds a BSc in Mathematics from the American University of Sharjah. Her research interests are in structural graph theory, discrete math, and graph coloring. Her recent work focuses on graph coloring reconfiguration problems.
DATE: December 29, Monday @ 10:30
Place: Zoom
Join Zoom at https://zoom.us/j/4924100806?pwd=dzZQMm9UTDRQbmJXRXd0bTFRb0UxZz09