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

Research & business

Research lectures, seminars and events

The events listed in this area are research seminars, workshops and lectures hosted by Durham University departments and research institutes. If you are not a member of the University, but  wish to enquire about attending one of the events please contact the organiser or host department.


December 2019
November 2019 January 2020
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31

Events for 3 December 2019

Andrei Krokhin: NP-hardness of 3-colouring (2+epsilon)-colourable graphs

1:00pm, 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 for more information about this event.