Graph homomorphism reconfiguration and frozen H‐colorings

For a fixed graph H, the reconfiguration problem for H‐colorings (ie, homomorphisms to H) asks: given a graph G and two H‐colorings φ and ψ of G, does there exist a sequence f0,…,fm of H‐colorings such that f0=φ, fm=ψ, and fi(u)fi+1(v)∈E(H) for every 0≤i

Saved in:
Bibliographic Details
Published in:Journal of graph theory 2020-07, Vol.94 (3), p.398-420
Main Authors: Brewster, Richard C., Lee, Jae‐Baek, Moore, Benjamin, Noel, Jonathan A., Siggers, Mark
Format: Article
Language:English
Subjects:
Coloring
complexity
graph homomorphism
Homomorphisms
Polymorphism
Polynomials
recoloring
Reconfiguration
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:For a fixed graph H, the reconfiguration problem for H‐colorings (ie, homomorphisms to H) asks: given a graph G and two H‐colorings φ and ψ of G, does there exist a sequence f0,…,fm of H‐colorings such that f0=φ, fm=ψ, and fi(u)fi+1(v)∈E(H) for every 0≤i
ISSN:0364-9024
1097-0118
DOI:10.1002/jgt.22530