Search

Given a graph $G$ and two graph homomorphisms $\alpha$ and $\beta$ from $G$ to a fixed graph $H$, the problem $H$-Recoloring asks whether there is a transformation from $\alpha$ to $\beta$ that changes the image of a single vertex at each step and keeps a graph homomorphism throughout. The complexity of the problem depends among other things on the presence of loops on the vertices. We provide a simple reduction that, using a known algorithmic result for $H$-Recoloring for square-free irreflexive graphs $H$, yields a polynomial-time algorithm for $H$-Recoloring for square-free reflexive graphs $H$. This generalizes all known algorithmic results for $H$-Recoloring for reflexive graphs $H$. Furthermore, the construction allows us to recover some of the known hardness results. Finally, we provide a partial inverse of the construction for bipartite instances., Comment: 12 pages, 2 figures

Gonz\'alez-Meneses, Manch\'on, and Silvero showed that the (hypothetical) extreme Khovanov homology of a link diagram is isomorphic to the reduced (co)homology of the independence simplicial complex of its Lando graph. Przytycki and Silvero conjectured that the extreme Khovanov homology of any link diagram is torsion-free. In this paper, we investigate explicit geometric realizations of the real-extreme Khovanov homology of pretzel links. This gives further support for the conjecture., Comment: 15 pages, 13 figures