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 firstname.lastname@example.org for more information