Mixing is hard for triangle-free reflexive graphs

DOI10.1016/J.EJC.2023.103860MaRDI QIDQ6146497zbMATH OpenFDO

Authors Hyobeen Kim, J. B. Lee, Mark Siggers

Publication date 5 February 2024

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2207.03632

zbMATH Keywords

simplicial complexHom-graph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Connectivity (05C40) Combinatorial aspects of simplicial complexes (05E45)

Abstract: In the problem $mMix(H)$ one is given a graph $G$ and must decide if the Hom-graph $$ is connected. We show that if $H$ is a triangle-free reflexive graph with at least one cycle, $mMix(H)$ is $mcoNP$-complete. The main part of this is a reduction to the problem $$ for a simplicial complex $$, in which one is given a simplicial complex $$ and must decide if there are any simplicial maps $phi$ from $$ to $$ under which some $1$-cycles of $$ maps to homologically non-trivial cycle of $$. We show that for any reflexive graph $H$, if the clique complex $$ of $H$ has a free, non-trivial homology group $$, then $$ is $mNP$-complete.

Recommendations

• Recolouring homomorphisms to triangle-free reflexive graphs
• Characterizing circular colouring mixing for pq<4 $\frac{p}{q}\lt 4$
• Reconfiguring graph homomorphisms on the sphere
• On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
• Homomorphisms of hexagonal graphs to odd cycles

Cites work

• scientific article; zbMATH DE number 2103273 (Why is no real title available?)
• A proof of the CSP dichotomy conjecture
• Characterizing circular colouring mixing for pq<4 $\frac{p}{q}\lt 4$
• Gibbs measures and dismantlable graphs
• Homomorphism reconfiguration via homotopy
• Introduction to reconfiguration
• Mixing 3-colourings in bipartite graphs
• Recolouring homomorphisms to triangle-free reflexive graphs
• Reconfiguration of homomorphisms to reflexive digraph cycles
• Reconfiguring graph homomorphisms on the sphere
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies

This page was built for publication: Mixing is hard for triangle-free reflexive graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6146497)