TY - JOUR

T1 - Recolouring homomorphisms to triangle-free reflexive graphs

AU - Lee, Jae baek

AU - Noel, Jonathan A.

AU - Siggers, Mark

N1 - Publisher Copyright:
© 2022, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.

PY - 2023/2

Y1 - 2023/2

N2 - For a graph H, the H-recolouring problem Recol (H) asks, for two given homomorphisms from a given graph G to H, if one can get between them by a sequence of homomorphisms of G to H in which consecutive homomorphisms differ on only one vertex. We show that, if G and H are reflexive and H is triangle-free, then this problem can be solved in polynomial time. This shows, at the same time, that the closely related H-reconfiguration problem Recon (H) of deciding whether two given homomorphisms from a given graph G to H are in the same component of the Hom-graph Hom (G, H) , can be solved in polynomial time for triangle-free reflexive graphs H.

AB - For a graph H, the H-recolouring problem Recol (H) asks, for two given homomorphisms from a given graph G to H, if one can get between them by a sequence of homomorphisms of G to H in which consecutive homomorphisms differ on only one vertex. We show that, if G and H are reflexive and H is triangle-free, then this problem can be solved in polynomial time. This shows, at the same time, that the closely related H-reconfiguration problem Recon (H) of deciding whether two given homomorphisms from a given graph G to H are in the same component of the Hom-graph Hom (G, H) , can be solved in polynomial time for triangle-free reflexive graphs H.

KW - Computational complexity

KW - Graph recolouring

KW - Homomorphism reconfiguration

KW - Reflexive graph

UR - http://www.scopus.com/inward/record.url?scp=85136200672&partnerID=8YFLogxK

U2 - 10.1007/s10801-022-01161-y

DO - 10.1007/s10801-022-01161-y

M3 - Article

AN - SCOPUS:85136200672

SN - 0925-9899

VL - 57

SP - 53

EP - 73

JO - Journal of Algebraic Combinatorics

JF - Journal of Algebraic Combinatorics

IS - 1

ER -