A topological proof of the H-colouring dichotomy

Add to your list(s) Download to your calendar using vCal

• Jakub Oprsal (University of Birmingham)
• Friday 09 May 2025, 14:00-15:00
• SS03, Computer Laboratory.

If you have a question about this talk, please contact Anuj Dawar.

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).

This talk is part of the Logic and Semantics Seminar (Computer Laboratory) series.

This talk is included in these lists:

• All Talks (aka the CURE list)
• Cambridge talks
• Computing and Mathematics
• Department of Computer Science and Technology talks and seminars
• Interested Talks
• Logic and Semantics Seminar (Computer Laboratory)
• SS03, Computer Laboratory
• School of Technology
• Trust & Technology Initiative - interesting events
• bld31
• tcw57’s list
• yk373's list

Note that ex-directory lists are not shown.