The approximate graph colouring problem (AGC) consists in finding a \(d\) -colouring of a given
\(c\) -colourable graph, where \(3\le c\le d\) . There is a huge gap in our
understanding of this problem.
For an \(n\) -vertex graph and \(c=3\) , the currently best known polynomial-time
algorithm of Kawarabayashi and Thorup [1]} finds a \(d\) -colouring of the graph with \(d=O(n^{0.19996})\) , building on a long line of works started by Wigderson [2]}.
It was conjectured by Garey and Johnson [3]} that the problem is NP-hard for any fixed constants
\(3\le c\le d\)  even in the decision variant: Given a graph, output \(\textsc {Yes}\)  if
it is \(c\) -colourable and output \(\textsc {No}\)  if it is not \(d\) -colourable.
