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.
Algorithms and Complexity (ACiD) Seminar: NP-hardness of 3-colouring (2+epsilon)-colourable graphs
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 email@example.com for more information