Master’s Thesis Presentation • Algorithms and Complexity — Building a Larger Class of Graphs for Efficient Reconfiguration of Vertex ColouringExport this event to calendar

Wednesday, May 6, 2020 — 1:30 PM EDT

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

Location 
Online presentation
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
1
2
3
4
  1. 2020 (155)
    1. September (1)
    2. August (20)
    3. July (14)
    4. June (19)
    5. May (17)
    6. April (20)
    7. March (17)
    8. February (25)
    9. January (22)
  2. 2019 (255)
    1. December (21)
    2. November (25)
    3. October (16)
    4. September (20)
    5. August (18)
    6. July (12)
    7. June (23)
    8. May (23)
    9. April (32)
    10. March (25)
    11. February (16)
    12. January (24)
  3. 2018 (220)
  4. 2017 (36)
  5. 2016 (21)
  6. 2015 (36)
  7. 2014 (33)
  8. 2013 (23)
  9. 2012 (4)
  10. 2011 (1)
  11. 2010 (1)
  12. 2009 (1)
  13. 2008 (1)