Reconfiguration of digraph homomorphisms

DOI10.1137/23M1623690MaRDI QIDQ7030691zbMATH OpenFDO

Authors Benjamin Lévêque, Moritz Mühlenthaler, Thomas Suzan

Publication date 7 February 2025

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/23M1623690

zbMATH Keywords

combinatorial reconfigurationdigraph homomorphismsgraph algorithmshomotopy equivalence

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Directed graphs (digraphs), tournaments (05C20) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Cites work

• A computational trichotomy for connectivity of Boolean satisfiability
• A dichotomy theorem for circular colouring reconfiguration
• A dichotomy theorem for nonuniform CSPs
• A proof of the CSP dichotomy conjecture
• Finding paths between 3-colorings
• Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
• Homomorphism complexes, reconfiguration, and homotopy for directed graphs
• Homomorphism reconfiguration via homotopy
• Introduction to reconfiguration
• On the complexity of reconfiguration problems
• Recolouring homomorphisms to triangle-free reflexive graphs
• Recolouring reflexive digraphs
• Reconfiguration of digraph homomorphisms
• Reconfiguration of homomorphisms to reflexive digraph cycles
• Reconfiguring graph homomorphisms on the sphere
• Reconfiguring spanning and induced subgraphs
• The complexity of change
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies

Cited in

(2)

• Homotopy types of Hom complexes of graph Homomorphisms whose codomains are square-free
• Homotopy types of Hom complexes of graph homomorphisms whose codomains are cycles

This page was built for publication: Reconfiguration of digraph homomorphisms

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