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