For \(c=d\) , the problem becomes the classic \(c\) -colouring problem, which appeared
on Karp's original list of 21 NP-complete problems [1]}. The case
\(c=3\) , \(d=4\)  was only proved to be NP-hard in 2000 by Khanna, Linial, and Safra [2]}
(and a simpler proof was given
by Guruswami and Khanna
in [3]}); more generally, [2]} showed hardness of the case
\(d=c+2{c/3}-1\) . This was improved to \(d=2c-2\)  in 2016 by Brakensiek and Guruswami [5]}, and recently to \(d=2c-1\)  by Barto, Bulín, Krokhin, and Opršal [6]}. In particular, this last result implies
hardness of the case \(c=3\) , \(d=5\) ; the complexity of the case \(c=3\) , \(d=6\)  is
still open. Building on the work of Khot [7]} and Huang [8]},
Krokhin, Opršal, Wrochna, and Živný established
NP-hardness for \(d={c\atopwithdelims (){c/2}}-1\) 
for \(c\ge 4\)  in [9]}.
NP-hardness of
AGC was established for all constants \(3\le c\le d\) 
by Dinur, Mossel, and Regev
in [10]} under a non-standard variant of
the Unique Games Conjecture,
by Guruswami and Sandeep
in [11]}
under the \(d\) -to-1 conjecture [12]} for any fixed \(d\) , and (an even stronger statement of distinguishing 3-colourability from not having an independent set of significant size)
by Braverman, Khot, Lifshitz, and Minzer
in [13]} under the rich 2-to-1 conjecture of Braverman, Khot, and Minzer [14]}.
