TY - JOUR
T1 - Mixing is hard for triangle-free reflexive graphs
AU - Kim, Hyobeen
AU - Lee, Jae baek
AU - Siggers, Mark
N1 - Publisher Copyright:
© 2023 Elsevier Ltd
PY - 2024/2
Y1 - 2024/2
N2 - In the problem Mix(H) one is given a graph G and must decide if the Hom-graph Hom(G,H) is connected. We show that if H is a triangle-free reflexive graph with at least one cycle, Mix(H) is coNP-complete. The main part of this is a reduction to the problem NonFlat(H) for a simplicial complex H, in which one is given a simplicial complex G and must decide if there are any simplicial maps ϕ from G to H under which some 1-cycles of G maps to homologically nontrivial cycle of H. We show that for any reflexive graph H, if the clique complex H of H has a free, nontrivial homology group H1(H), then NonFlat(H) is NP-complete.
AB - In the problem Mix(H) one is given a graph G and must decide if the Hom-graph Hom(G,H) is connected. We show that if H is a triangle-free reflexive graph with at least one cycle, Mix(H) is coNP-complete. The main part of this is a reduction to the problem NonFlat(H) for a simplicial complex H, in which one is given a simplicial complex G and must decide if there are any simplicial maps ϕ from G to H under which some 1-cycles of G maps to homologically nontrivial cycle of H. We show that for any reflexive graph H, if the clique complex H of H has a free, nontrivial homology group H1(H), then NonFlat(H) is NP-complete.
UR - http://www.scopus.com/inward/record.url?scp=85173221330&partnerID=8YFLogxK
U2 - 10.1016/j.ejc.2023.103860
DO - 10.1016/j.ejc.2023.103860
M3 - Article
AN - SCOPUS:85173221330
SN - 0195-6698
VL - 116
JO - European Journal of Combinatorics
JF - European Journal of Combinatorics
M1 - 103860
ER -