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.
The ACO Seminar (2019–2020)