March 28, 2022
Jakub Opršal (Oxford)As almost everybody knows, deciding whether a given graph is colourable using 3 colours is an NP-hard problem which means that finding a 3-colouring of a graph that is promised to be 3-colourable cannot be achieved in polynomial time, unless P = NP.
But how hard is to find a colouring of such a graph using 4, 5, 6, or more colours?
Surprisingly little is known to that account — it has only recently (in 2019) been shown that finding a 5-colouring of a given 3-colourable graph is NP-hard, while the best known polynomial algorithm, due to Kawarabayashi and Thorup, uses a little less than $O(n^{1/5})$ colours where $n$ is the number of vertices of the input graph.
We will present several recent advancements on this problem, and their relevance to a wider scope of promise constraint satisfaction.
The promise constraint satisfaction problem is a natural generalisation of both the above promise version of graph colouring and the constraint satisfaction problem (CSP). This generalised, promise variant gained a substantial attention in recent years due to generalisation of algebraic techniques behind the theory of CSP, that lead to the famous CSP dichotomy, to the promise setting.