Reconfiguration of homomorphisms to reflexive digraph cycles

DOI10.1016/J.DISC.2021.112441zbMath1466.05137OpenAlexW3160395046MaRDI QIDQ2032862

Jae-Baek Lee, Mark H. Siggers, Richard C. Brewster

Publication date: 14 June 2021

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2021.112441

zbMATH Keywords

graph homomorphismreflexive digraphreconfigurationrecolouringHom-graph

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (1)

Mixing is hard for triangle-free reflexive graphs

Cites Work

• A dichotomy theorem for circular colouring reconfiguration
• Reflexive digraphs with near unanimity polymorphisms
• Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
• Recolouring reflexive digraphs
• Connectedness of the graph of vertex-colourings
• Homomorphism reconfiguration via homotopy
• A polynomial-time algorithm for near-unanimity graphs
• Mixing Homomorphisms, Recolorings, and Extending Circular Precolorings
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory

This page was built for publication: Reconfiguration of homomorphisms to reflexive digraph cycles