| Speaker: | Hidde Koerts |
| Affiliation: | University of Waterloo |
| Room: | MC 6029 |
Abstract: Determining whether a graph is k-colourable is a famously hard computational problem. Even when placing significant restrictions on the graph, the resulting problem is often NP-hard. In this talk, we focus on the case of restricting the diameter. Under the Exponential Time Hypothesis, there does not exist a sub-exponential algorithm for 3-colouring diameter-4 graphs or for 4-colouring diameter-2 graphs. Hence, the interesting remaining cases are 3-colouring graphs of diameter 2 or 3. We show that 3-colouring diameter-3 graphs can be solved in 2^O(n^{2/3−ε}) for any ε < 1/33 by providing an algorithm based on a structural result. This improves on the previous best known algorithm due to Dębski, Piecyk and Rzążewski.
This talk is based on joint work with Carla Groenland and Sophie Spirkl.