## Dr. Naomi Nishimura

When:Tuesday, 23rd October 2018 1:00 pm

Where: E2-320
Title: Reconfiguring Subgraphs and Graph Minors

In this talk, I will present two recent results in the area of combinatorial reconfiguration, in the process providing both a primer for those unfamiliar with the reconfiguration framework and insights into new directions for those already familiar with previous work in the area. Reconfiguration provides a way of exploring the relationships among configurations (typically solutions to an instance of a problem), where a reconfiguration step transforms one configuration into another by a small, incremental change.

In the result on subgraphs, each configuration is a subset of edges or vertices of an input graph that form a subgraph in a specified class. We consider the complexity of determining whether or not one configuration can be transformed (or, is reconfigurable) to another by a sequence of reconfiguration steps for different choices of graph classes and representations of subgraphs.

In studying graph minors, we consider each configuration to be a labeling of the vertices of a graph G by the vertices of a graph H. We then determine the properties of both G and H that result in each configuration being reconfigurable to any other.

No previous knowledge of reconfiguration or graph minors is assumed.

Complete Seminar List