Mixing is hard for triangle-free reflexive graphs

Hyobeen Kim, Jae baek Lee, Mark Siggers

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish
Article number103860
JournalEuropean Journal of Combinatorics
Volume116
DOIs
StatePublished - Feb 2024

Fingerprint

Dive into the research topics of 'Mixing is hard for triangle-free reflexive graphs'. Together they form a unique fingerprint.

Cite this