November 7, 3:30pm, Wean 7218 (note the room change)

Jakub Opršal, Durham University

Topology in computational complexity of graph colouring problems

Jakub Opršal, Durham University

Topology in computational complexity of graph colouring problems

Abstract:

It is widely believed that colouring a given graph that is promised to be 3-colourable using constant number of colours cannot be achieved in polynomial time unless P = NP. We will discuss a related computational problem: Namely, instead of relaxing the number of colours used, we insist to find a 3-colouring, but instead strengthen our promise. The problem is then to find a 3-colouring of a graph that is promised to have a homomorphism (an edge-preserving map) to some 3-colourable non-bipartite graph H. We will show that this problem is still NP-hard. Surprisingly, the solution uses several ideas from algebraic topology. We will explore how are these ideas used, and a possibility of extending them to provide classification of computational complexity of similar problems.

Before the talk, at 3:10pm, there will be tea and cookies in Wean 6220.