In the problem ${ \rm Mix}(H)$ one is given a graph $G$ and must decide if the Hom-graph ${ \rm { \bf Hom}}(G,H)$ is connected. We show that if $H$ is a triangle-free reflexive graph with at least one cycle, ${ \rm Mix}(H)$ is ${ \rm coNP}$-complete. The main part of this is a reduction to the problem ${ \rm NonFlat}({ \rm{ \bf H}})$ for a simplicial complex ${ \rm{ \bf H}}$, in which one is given a simplicial complex ${ \rm{ \bf G}}$ and must decide if there are any simplicial maps $\phi$ from ${ \rm{ \bf G}}$ to ${ \rm{ \bf H}}$ under which some $1$-cycles of ${ \rm{ \bf G}}$ maps to homologically non-trivial cycle of ${ \rm{ \bf H}}$. We show that for any reflexive graph $H$, if the clique complex ${ \rm{ \bf H}}$ of $H$ has a free, non-trivial homology group $H_1({ \rm{ \bf H}})$, then ${ \rm NonFlat}({ \rm{ \bf H}})$ is ${ \rm NP}$-complete.
Categories: math.CO