Mixing is hard for triangle-free reflexive graphs

DOI10.1016/J.EJC.2023.103860arXiv2207.03632MaRDI QIDQ6146497FDOQ6146497

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

Publication date: 5 February 2024

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

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.

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

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

zbMATH Keywords

simplicial complexHom-graph

Mathematics Subject Classification ID

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

Cites Work

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

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)