Jakub Oprsal: A topological proof of the H-colouring dichotomy

Abstract:

A colouring of a graph with k colours is an assignment of colours to vertices so that no edge is monochromatic. As it is well known colouring with 2 colours is in P while colouring with \(k > 2\) colours is NP-complete. This dichotomy was extended to the graph homomorphism problem, also called H-colouring, by Hell and Nešetřil [J. Comb. Theory B, 48(1):92-110, 1990]. More precisely, they proved that deciding whether there is a graph homomorphism from a given graph to a fixed graph H is in P if H is bipartite (or contains a self-loop), and is NP-complete otherwise. This dichotomy served as an important test-case for the Feder Vardi dichotomy conjecture, and Bulatov–Zhuk dichotomy of complexity of finite-template CSPs.

In the talk, I will present a new proof of this theorem using tools from topological combinatorics based on ideas of Lovász [J. Comb. Theory, Ser. A, 25(3):319-324, 1978] and Brower’s fixed-point theorem. This is joint work with Sebastian Meyer (TU Dresden).