Ben Moore, University of Waterloo
"A proof of the Hell-Neˇsetˇril Dichotomy via Siggers Polymorphism"
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