BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:A topological proof of the H-colouring dichotomy - Jakub Oprsal (U
 niversity of Birmingham)
DTSTART:20250509T130000Z
DTEND:20250509T140000Z
UID:TALK228988@talks.cam.ac.uk
CONTACT:Anuj Dawar
DESCRIPTION:A colouring of a graph with $k$ colours is an assignment of co
 lours to vertices so that no edge is monochromatic. As it is well-known co
 louring 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 t
 here 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 othe
 rwise. This dichotomy served as an important test-case for the Feder–Var
 di dichotomy conjecture\, and Bulatov–Zhuk dichotomy of complexity of fi
 nite-template CSPs.\n\nIn the talk\, I will present a new proof of this th
 eorem 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-po
 int theorem. This is joint work with Sebastian Meyer (TU Dresden).\n\n 
LOCATION:SS03\, Computer Laboratory
END:VEVENT
END:VCALENDAR