  We study the complexity of approximation on satisfiable instances for graph
homomorphism problems. For a fixed graph $H$, the $H$-colouring problem is to
decide whether a given graph has a homomorphism to $H$. By a result of Hell and
Ne\v{s}et\v{r}il, this problem is NP-hard for any non-bipartite graph $H$. In
the context of promise constraint satisfaction problems, Brakensiek and
Guruswami conjectured that this hardness result extends to promise graph
homomorphism as follows: fix any non-bipartite graph $H$ and another graph $G$
with a homomorphism from $H$ to $G$, it is NP-hard to find a homomorphism to
$G$ from a given $H$-colourable graph. Arguably, the two most important special
cases of this conjecture are when $H$ is fixed to be the complete graph on 3
vertices (and $G$ is any graph with a triangle) and when $G$ is the complete
graph on 3 vertices (and $H$ is any 3-colourable graph). The former case is
equivalent to the notoriously difficult approximate graph colouring problem. In
this paper, we confirm the Brakensiek-Guruswami conjecture for the latter case.
Our proofs rely on a novel combination of the universal-algebraic approach to
promise constraint satisfaction, that was recently developed by Barto, Bul\'in
and the authors, with some ideas from algebraic topology.
