Graphs and Matroids Seminar

Title: A characterization of (p,q)-mixing when p/q < 4

Abstract: Let Hom(G,H) be the graph whose vertex set is the set of H-colourings of G, and two H-colourings f and g are adjacent if f differs from g in at most one vertex. The H-mixing problem is to determine if Hom(G,H) is connected when given just H and G. In particular, when H is a circular clique on integers p and q, then this is called the (p,q)-mixing problem. I'll show that when 2< p/q < 4,  G is (p,q)-mixing if and only if for every (p,q)-colouring f, and every cycle C, the winding number of C under f is 0. When H is an odd cycle, this simplifies to G is (2k+1,k)-mixing if and only if G does not fold to C_6, where a fold is a restricted graph homomorphism. If time persists, I'll sketch a polynomial time algorithm for this problem when G is planar.