Graph Homomorphism Reconfiguration and Frozen H-Colourings

2017/12/01 by Brewster, Richard C., Lee, Jae-Baek, Moore, Benjamin +2
#05C60 #Combinatorics (math.CO) #Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.1712.00200

Abstract

For a fixed graph H, the reconfiguration problem for H-colourings (i.e. homomorphisms to H) asks: given a graph G and two H-colourings φ and ψ of G, does there exist a sequence f₀,…,f_m of H-colourings such that f₀=φ, f_m=ψ and f_i(u)f_i+1(v)∈ E(H) for every 0≤ i

Related

• Homomorphism reconfiguration via homotopy
• Reconfiguration of Digraph Homomorphisms
• Reconfiguring homomorphisms to reflexive graphs via a simple reduction
• Finding Shortest Paths between Graph Colourings
• Surjective H-Colouring: New Hardness Results