Cookies

We use cookies to ensure that we give you the best experience on our website. You can change your cookie settings at any time. Otherwise, we'll assume you're OK to continue.

Durham University

Computer Science

Seminars

 

Algorithms and Complexity (ACiD) Seminar: NP-hardness of 3-colouring (2+epsilon)-colourable graphs

Presented by Andrei Krokhin, Durham University
3 December 2019 13:00 in E245

It is well known that the problem of finding a 3-colouring of a given 3-colourable graph is NP-hard. A graph G has circular chromatic number at most 2+1/k iff G admits a homomorphism to a cycle on 2k+1 vertices. Every such graph G is clearly 3-colourable. We prove that, for any positive k, the problem of finding a 3-colouring of a given graph with circular chromatic number at most 2+1/k is NP-hard. This is joint work with Jakub Oprsal.

Contact algorithms.complexity@dur.ac.uk for more information