The graph homomorphism problem is a canonical $NP$-complete problem.
It generalizes various other well-studied problems such as graph
coloring and finding cliques. To get a better insight into a
combinatorial problem, one often studies relaxations of the problem.
We define fractional homomorphisms and pseudo-homomorphisms ... more >>>