All reports by Author Andrei Krokhin:

__
TR19-053
| 5th April 2019
__

Andrei Krokhin, Jakub Opršal#### 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 graph has a homomorphism to $H$. By a result of Hell and Nešet?il, this problem is NP-hard for any non-bipartite graph $H$. In ... more >>>