Complexity of the Graph Homomorphism Problem w.r.t. Degeneracy

Grigorii Braulov, Nikolai Chukhin, Alexander S. Kulikov +1

The graph homomorphism problem HOM is: given an $n$-vertex source graph $G$ and an $h$-vertex target graph $H$, is there a mapping from $V(G)$ to $V(H)$ that preserves edges? A str…