2024/10/16 by Moritz Mühlenthaler, Mühlenthaler, Moritz, Mark Siggers +3
Computer Science · #05C85 (Primary) 05C15 #68Q25 (Secondary) #Advanced Graph Theory Research #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Logic, programming, and type systems #Model-Driven Software Engineering Techniques
paper · pdf · doi:10.48550/arxiv.2410.12687
openalex publication_date 2024/10/16 · openalex created_date 2024/10/21 · openalex updated_date 2026/07/28
Given a graph G and two graph homomorphisms α and β from G to a fixed graph H, the problem H-Recoloring asks whether there is a transformation from α to β that changes the image of a single vertex at each step and keeps a graph homomorphism throughout. The complexity of the problem depends among other things on the presence of loops on the vertices. We provide a simple reduction that, using a known algorithmic result for H-Recoloring for square-free irreflexive graphs H, yields a polynomial-time algorithm for H-Recoloring for square-free reflexive graphs H. This generalizes all known algorithmic results for H-Recoloring for reflexive graphs H. Furthermore, the construction allows us to recover some of the known hardness results. Finally, we provide a partial inverse of the construction for bipartite instances.