Pure Math and C&O Joint Colloquium

Ben Moore, University of Waterloo

In 2017, the constraint satisfaction dichotomy was proven via techniques from universal algebra. If we restrict this theorem to graphs, we get the Hell-Neˇsetˇril Dichotomy, which is a statement about colouring graphs. It says that for a fixed graph H, determining if a graph G admits an H- colouring is NP-complete if and only if H does not contain a loop, and H is not bipartite. The original proof is graph theoretic, but I’ll present a proof using more algebraic techniques due to Mark Siggers which should be accessible to everyone.

MC 4020