Master’s Thesis Presentation • Algorithms and Complexity — Building a Larger Class of Graphs for Efficient Reconfiguration of Vertex Colouring

Wednesday, May 6, 2020 1:30 pm - 1:30 pm EDT (GMT -04:00)

Please note: This master’s thesis presentation will be given online.

Owen Merkel, Master’s candidate
David R. Cheriton School of Computer Science

For a graph G, the reconfiguration graph of the k-colourings is the graph whose vertices are the k-colourings of G and two colourings are joined by an edge if they differ in colour on exactly one vertex. For a k-colourable graph, we investigate the connectivity and diameter of the reconfiguration graph of the (k+1)-colourings. We introduce a new class of graphs called OAT graphs that are built from four simple operations, disjoint union, join, and the addition of a clique or comparable vertex. We prove that if G is a k-colourable OAT graph, then the reconfiguration graph of the (k+1)-colourings is connected with diameter O(n^2). Furthermore, we give polynomial time algorithms to recognize OAT graphs and to find a path between any two colourings in the reconfiguration graph.

To join this master’s thesis presentation on Zoom, please go to https://us02web.zoom.us/j/88124314731?pwd=RkZpTUh2Ry9XMEh0RDVpKzNuRk1JUT09

Meeting ID: 881 2431 4731
Password: 041800