The complexity of 3-colouring $H$-colourable graphs

Andrei Krokhin, Jakub Opršal

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 gra…