Reconfiguration of homomorphisms to reflexive digraph cycles

DOI10.1016/J.DISC.2021.112441MaRDI QIDQ2032862zbMATH OpenOpenAlexFDO

Authors J. B. Lee, Richard C. Brewster, Mark Siggers

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 homomorphismHom-graphrecolouringreconfigurationreflexive digraph

Mathematics Subject Classification ID

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

Recommendations

• Recolouring reflexive digraphs
• Homomorphism reconfiguration via homotopy
• The Existence of Homomorphisms to Oriented Cycles
• Homomorphism reconfiguration via homotopy
• Recolouring homomorphisms to triangle-free reflexive graphs

Cites work

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

Cited in

(5)

• Recolouring reflexive digraphs
• Reflexive digraphs with near unanimity polymorphisms
• Mixing is hard for triangle-free reflexive graphs
• Reconfiguration of digraph homomorphisms
• Reconfiguration of digraph homomorphisms

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

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