title: Characterizing Circular Colouring Mixing for $\frac{p}{q}<4$
authors: Richard C. Brewster Benjamin Moore
text: 
  
  
  Given a graph G, the k-mixing problem asks: Starting with a k-colouring of G, can one obtain all k-colourings of G by changing the colour of only one vertex at a time, while at each step maintaining a k-colouring? More generally, for a graph H, the H-mixing problem asks: Can one obtain all homomorphisms G →  H, starting from one homomorphism f, by changing the image of only one vertex at a time, while at each step maintaining a homomorphism G → H?
  
  This paper focuses on a generalization of k-colourings, namely (p,q)-circular colourings. We show that when 2 < p/q < 4, a graph G is (p,q)-mixing if and only if for any (p,q)-colouring f of G, and any cycle C of G, the wind of the cycle under the colouring equals a particular value (which intuitively corresponds to having no wind).
  As a consequence we show that (p,q)-mixing is closed under a restricted homomorphism called a fold. Using this, we deduce that (2k+1,k)-mixing is co-NP-complete for all k ∈ℕ, and by similar ideas we show that if the circular chromatic number of a connected graph G is 2k+1/k, then G folds to C_2k+1. We use the characterization to settle a conjecture of Brewster and Noel, specifically that the circular mixing number of bipartite graphs is 2. 
  Lastly, we give a polynomial time algorithm for (p,q)-mixing in planar graphs when 3 ≤p/q <4.
  
  
  Graph Neural Network Architecture Search for 
   Molecular Property Prediction
  
  
      Shengli Jiang
  Department of Chemical and Biological Engineering 
  
  University of Wisconsin — Madison
  
  Madison, USA 
  
  sjiang87@wisc.edu
  Prasanna Balaprakash
  Mathematics and Computer Science Division & 
  
  Leadership Computing Facility 
  
  Argonne National Laboratory
  
  Lemont, USA 
  
  pbalapra@anl.gov
  
      December 30, 2023
  =========================================================================================================================================================================================================================================================================================================
  
  
  
  Keywords: graph theory, colouring, mixing, homomorphism, reconfiguration
  
  
  
  § ACKNOWLEDGEMENT
  
  We thank the referees for their helpful suggestions.
  The second author is grateful for discussions with Vijay Subramanya and Naomi Nishimura.
  
  
  
  § INTRODUCTION
  
  
  Combinatorial reconfiguration problems have received much attention in the recent literature <cit.>.  A particularly well-studied example is graph colouring reconfiguration <cit.>.  For a fixed positive integer k, the k problem takes as input a graph G together with two k-colourings f and g and asks if there is a sequence of k-colourings of G, f=f_0, f_1, …, f_l = g such that successive colourings in the sequence differ on a single vertex. In the affirmative we say f reconfigures to g. Using a standard reconfiguration framework, we define (G,K_k) to be the graph whose vertex set is the set of k-colourings of G with two k-colourings c_1, c_2 adjacent if c_1(v) ≠ c_2(v) for at most one vertex v ∈ V(G).  Clearly, f reconfigures to g precisely when there is a path from f to g in (G,K_k). Cereceda, van den Heuvel, and Johnson <cit.> show 3 is polynomial time solvable.  This is somewhat surprising given the 3-colouring problem itself is NP-complete. In comparison, Bonsma and Cereceda <cit.> show for all k ≥ 4, the k problem is PSPACE-complete. 
  
  In this paper, we study a related reconfiguration problem.  For a fixed k, the k problem takes as input a graph G and asks if (G,K_k) is connected. If yes, we say G is k-mixing. When k ≤ 2, it is easy to see that the k problem is in P, since G is 2-mixing if and only if G has no edges. For k =3, Cereceda, van den Heuvel and Johnson <cit.> show the 3 problem is co-NP-complete in general, and in P when the inputs are restricted to planar graphs.  The complexity of k is open for all k ≥ 4, and conjectured in <cit.> to be PSPACE-complete.
  
  By studying (p,q)-circular colourings (a refinement of k-colourings defined in Section <ref>) the dichotomy theorem in <cit.> is extended in <cit.> to the following.  The (p,q) problem is polynomial if 2 ≤p/q< 4 and is PSPACE-complete for p/q≥ 4. This result uses the ideas of <cit.>, but the more general setting highlights the key tool in the polynomial time algorithm.  In particular, the notion of cycle wind invariance (defined in Section <ref>) follows from the restriction p/q < 4, rather than, say, the number of colours available.  In general, the role of topological ideas in homomorphism reconfiguration appear in Wrochna's ground breaking works <cit.>.
  
  In this work, we extend the study of the mixing problem to (p,q)-circular colourings. 
  In brief, we prove the following characterization. For 2 < p/q < 4, a graph G is (p,q)-mixing if and only if for any (p,q)-circular colouring of G, and any cycle C of G, the wind of the cycle under the colouring equals a particular value (which intuitively corresponds to having no wind).  This results extends the work of <cit.> from k=3 to the range 2 < p/q < 4.
  
  As a consequence, we show that (p,q)-mixing is closed under a restricted, wind preserving, homomorphism called a fold. Using this, we prove that (2k+1,k)-mixing is co-NP-complete for all k ∈ℕ, extending the k=3 result in <cit.>.  By similar ideas we show that if the circular chromatic number of a connected graph G is 2k+1/k, then G folds to C_2k+1. This complements the result of Cook and Evans <cit.> stating that a graph with chromatic number k folds to K_k.  (Zhu <cit.> shows that such folding results for other values of p/q is not possible.) We use the mixing characterization to settle a conjecture of Brewster and Noel in the positive, specifically that the circular mixing number of bipartite graphs is 2. Lastly, we give a polynomial time algorithm for (p,q)-mixing for planar graphs when 3 ≤p/q <4.
  
  Thus, our work maybe viewed as a refinement of the 3-mixing results in <cit.>.  By studying (p,q)-colourings for 2 ≤p/q < 4 (of which k = p/q = 3 is a special case) we see some results extend to the entire range 2  ≤p/q < 4, the co-NP-completeness results extend to odd cycles (of which K_3 is a special case) and finally the planar complexity results extend to 3 ≤p/q < 4 (again of which k=3 is a special case).  In the latter two settings, we provide evidence that extending the folding results beyond odd cycles and the planar results to 2< p/q < 3 will be challenging.
  
  The following section contains key definitions, statements of our main results, and an outline of the paper.  
  
  
  
  
  
  § DEFINITIONS AND STATEMENTS OF RESULTS
  
  
  In this work we consider finite, simple graphs.  We refer the reader to <cit.> for standard graph theoretic terminology and notation.
  
  The key focus of this paper is extending results on k-mixing to circular colourings. We first define such colourings. Let p, q be positive integers. A (p,q)-circular colouring of a graph G=(V,E) is a labelling of the vertices f:V →{ 0, 1, 2, …, p-1 } such that if uv ∈ E, then q ≤ |f(u)-f(v)| ≤ p-q.  That is, adjacent vertices receive labels differing by at least q in the circular sense, i.e. |x-y| = min{ |x-y|, |p-x+y| }.  For brevity we drop the word circular and use the term (p,q)-colouring throughout the paper.  When q=1 the condition reduces to adjacent vertices receiving different colours, hence (p,q)-colourings generalize k-colourings.  Thus, one may view our work here and in <cit.> as extending the works of Cereceda et al. from k = 3 to 2 < p/q < 4.
  
  It is convenient, and common, to define colourings via graph homomorphisms. (See <cit.> for a detailed treatment of graph homomorphisms.) Given graphs G and H, a homomorphism f from G to H is a mapping f:V(G) → V(H) such that for any edge uv ∈ E(G), f(u)f(v) ∈ E(H). We write f: G → H or simply G → H to indicate the existence of a homomorphism from G to H.  Owing to the fact that a k-colouring of G is a homomorphism G → K_k, in general a homomorphism of G → H is called an H-colouring of G.  Circular colourings are graph homomorphisms to specific target graphs called circular cliques. (See <cit.> for a complete development.) Let p and q be positive integers such that p/q≥ 2. Define the (p,q)-circular clique, G_p,q, to have vertex set V(G_p,q) = {0,…,p-1} and edge set uv ∈ E(G_p,q) if and only if q ≤ |u-v| ≤ p-q. Thus, a (p,q)-colouring of a graph G is a homomorphism G → G_p,q.  Note that G_k,1≅ K_k and again we note circular colourings generalize k-colourings.
  
  Bondy and Hell <cit.> show G_p,q→ G_p',q' if and only if p/q≤p'/q'.  As homomorphisms compose, if G → G_p,q, then G → G_p',q' for all p'/q'≥p/q.    Moreover, in <cit.>, they show there is a minimum p/q such that G → G_p,q.  We called this minimum value the circular chromatic number and denote it by χ_c(G).  In particular, ⌈χ_c(G) ⌉ = χ(G) showing the circular chromatic number is a refinement of the chromatic number.  
  
  One can ask reconfiguration questions about H-colourings for general H. There are many papers studying such questions, see for instance <cit.>. Given graphs G and H, the graph (G,H) has as vertices all homomorphisms from G to H with two homomorphisms f and g adjacent if f(v) ≠ g(v) for at most one vertex v ∈ V(G). (This definition implies (G,H) is reflexive, i.e. has a loop on each vertex.  For readers familiar with the exponential graph H^G, the reconfiguration graph (G,H) is then a spanning subgraph of the reflexive subgraph of H^G. See for example <cit.>.)  Thus, in general we define the H problem as taking two homomorphism f, g: G → H and asking if there is a path from f to g in (G,H).  The H problem takes as input a graph G and asks if (G,H) is connected.
  
  In this work we study the mixing problem for (p,q)-colourings.  Namely, for a graph G we characterize when (G, G_p,q) is connected and we examine the computational complexity of determining if (G,G_p,q) is connected.  If G is a yes instance to the G_p,q problem, we say G is (p,q)-mixing. Of particular interest in this paper are (2k+1,k)-colourings.  Since G_2k+1,k≅ C_2k+1, our results on (2k+1,k)-mixing are often stated as results for odd cycles.
  Our first two main results generalize the Cereceda, van den Heuvel, Johnson 3 complexity results to odd cycles for general inputs and for planar inputs to all 3 ≤p/q < 4. We note that Theorem <ref> encompasses all known complexity results on the H problem for general inputs.
  
  
  
  The C_2k+1 problem is co-NP-complete for all k ∈ℤ^+.
  
  
   
  
  Let G be a planar graph and let p and q be positive integers where 3 ≤p/q < 4. Then it can be determined in polynomial time whether G is (p,q)-mixing. 
   
  
  Based on Theorem <ref>, the results in  <cit.>, and the conjecture that the k problem is PSPACE-complete for k ≥ 4, the following conjecture is natural:
  
  
  If p/q = 2, then G_p,q is in P. If 2 < p/q < 4, then G_p,q is co-NP-complete. If p/q≥ 4, then G_p,q is PSPACE-complete. 
  
  
  Note the G_p,q problem is trivial when p/q = 2 as a graph G is (p,q)-mixing if and only if G has no edges.
  
  Our third result and our key contribution is the following structural characterization of (p,q)-mixing when 2 < p/q < 4 from which Theorem <ref> and Theorem <ref> follow.  To state the characterization we require the following definitions. Let G be a graph and let f be a (p,q)-colouring of G. Given an edge uv of G, define the weight of uv under f as W(uv,f) = (f(v) - f(u)) p. Note there is an implied direction to uv here.  The following two observations are used throughout the paper.
  
  
  Let G be a graph and f be a (p,q)-colouring of G. 
  (enumi)enumi
    
    * For an edge uv in G, W(uv,f) = - W(vu,f) p = p - W(vu,f).
    
    * For a path of length 2, uvw, with f(u) = f(w), W(uv,f)+W(vw,f) = p.
  
  
  
  Given a set of edges from G, S ⊆ E(G), we naturally extend the concept of weight by
  
      W(S,f) = ∑_uv ∈ S W(uv,f).
  
  Given a walk X = x_0, x_1, x_2, …, x_l in G, as a slight abuse of notation we write
  
      W(X,f) = ∑_i=1^l W(x_i x_i-1, f).
  
  In particular for a cycle of length l, C = c_0, c_1, …, c_l-1, c_0,
  
      W(C,f) = ∑_i=1^l W(c_i c_i-1,f),
  
  where index arithmetic is modulo l.  For a cycle C, the sum telescopes and hence 
  
      W(C,f) = p · w_f(C)  w_f(C).
   
  We call w_f(C) the wind of C under f.
  
  As an example, consider two (5,2)-colourings of C_10 (on vertex set { c_i | 0 ≤ i ≤ 9}). Define f by f(c_i) = 2i 5 and g(c_i) = 0 if i is even and g(c_i)=2 if i is odd.  Then W(C_10,f) = 20 and w_f(C_10) = 4. Similarly, W(C_10,g) = 25 and w_g(C_10) = 5. On the other hand, any (5,2)-colouring of C_8 will have wind 4.
  
  Now we can state the theorem.
  
  
  
  Fix integers p,q ∈ℤ such that 2 < p/q < 4. A graph G is (p,q)-mixing if and only if for every (p,q)-colouring f, and for every cycle C in G, the wind of C under f is |E(C)|/2. 
  
  
  It follows from this characterization, that to certify G is not (p,q)-mixing, we simply need to exhibit a (p,q)-colouring and a cycle without the required winding number. Hence, we have a concise NO-certificate and thus G_p,q is in co-NP when 2 < p/q < 4. 
  The invariance of wind under reconfiguration turns out to be the key tool in both <cit.> rather than say the number of colours available. Indeed the colourings under study in these previous works, this invariance can be shown to follow from the fact that four cycles must have wind 2. This is made explicit in <cit.>. 
  
  
  While Theorem <ref> characterizes (p,q)-mixing for all 2 < p/q < 4, our co-NP-completeness result is for the special case of (2k+1,k)-colourings. (These are the 2-regular circular cliques and thus extend the results for 3-colourings in <cit.>). Our result for (2k+1,k)-mixing exploits a  restricted homomorphism called a fold, which we define now.  Given a graph G, and two vertices x and y at distance 2, let G_xy be the graph obtained by identifying x and y. Call the new vertex v_xy.  The homomorphism f: G → G_xy defined by f(x) = f(y) = v_xy and f(u)=u for u ∉{x,y} is an elementary fold. We say a graph G folds to a graph H if there is a homomorphism f: G → H where f is a composition of elementary folds and f(G) is isomorphic to H. We call such a mapping a folding.
  
  We now state our next result.
  
  
  
  Fix integers p,q such that 2 < p/q < 4. Suppose  G folds to H. If H is not (p,q)-mixing, then G is not (p,q)-mixing. In particular, for p = 2q+1, a bipartite, connected graph G is (p,q)-mixing if and only if G does not fold to C_4q+2. 
  
  
  We use Theorem <ref>  to resolve a conjecture in <cit.> in the affirmative:
  
  
  
  For every bipartite graph G, there exists an integer k ∈ℤ such that G is C_2k+1-mixing.
  
  
  Theorem <ref> follows from Theorem <ref> by showing that testing if an input graph G folds to C_4q+2 is NP-complete. For this final step, we build on a theorem of Vikas <cit.>. 
  We conjecture that Theorem <ref> can be generalized to all 2 < p/q < 4 by allowing a finite family of forbidden folding targets.
  
  
  
  
  Fix integers p,q such that 2 < p/q < 4. Then there is a finite family of graphs 𝒢_p,q such that G is (p,q)-mixing if and only if G does not fold to a graph H ∈𝒢_p,q. 
  
  
  In Section <ref> we prove Theorem <ref>. Given two (p,q)-colourings f and g (2 < p/q < 4) of a graph G, the characterization in <cit.> asserts f reconfigures to g, if for every cycle C in G, w_f(C)=w_g(C), and further, the set of fixed vertices (vertices which can never change colour under reconfiguration) and their images are the same under both f and g.  We show the existence of fixed vertices implies the existence of a cycle C whose wind is not |E(C)|/2. We then argue that given a (p,q)-colouring f and a cycle C whose wind is not |E(C)|/2, we can define a new (p,q)-colouring g such that w_f(C) ≠ w_g(C). The characterization in <cit.> gives that f does not reconfigure to g, and hence the graph is not (p,q)-mixing. The converse of Theorem <ref> follows similarly by appealing to the characterization in <cit.>.
  
  In Section <ref> we prove Theorem <ref>, Theorem <ref> and Theorem <ref>. To prove Theorem <ref> we analyse how folding impacts the winds of cycles, and then appeal to Theorem <ref>. A consequence of Theorem <ref> is the following.  Let G be a bipartite graph that is not (p,q)-mixing.  Since G is bipartite, it folds to K_2.  This folding produces a sequence of graphs starting at G and ending at K_2.  In the sequence there is a graph H such that H and all its predecessors are not (p,q)-mixing while all successors of H are (p,q)-mixing.  In the special case of C_2k+1-mixing, we prove such a sequence can be found where H = C_4k+2.   From this characterization, Theorem <ref> follows easily. 
  
  In Section <ref> we prove Theorem <ref>. The general approach is similar to the approach taken for 3 in <cit.>. We first argue that our graph can be assumed to be 2-connected. Next, we argue for any 2 < p/q < 4, if the graph has 
  a planar embedding with at most one large face (large depends on p and q), then it is (p,q)-mixing.  The converse holds in the absence of short separating cycles (short depends on p and q); however, the general situation seems complicated.  When 3 ≤p/q <4, we show that we can decompose the graph into subgraphs with no short separating cycles (specifically C_4) and apply the characterization to each subgraph.
  The polynomial time algorithm follows easily from this, as the blocks can can be found in polynomial time as can all separating 4-cycles.  Once decomposed, listing the face lengths of a planar embedding can be done in polynomial time.
  By contrast we give some examples when 2 < p/q < 3 where we cannot decompose our graph to have no small separating cycles, showing that the situation is more complex.
   
  
  
  
  
  
  § CHARACTERIZING MIXING BY CYCLE WINDS
  
  
  
  In this section, for 2 ≤p/q < 4, we characterize graphs that are (p,q)-mixing. As noted above, for p/q = 2, G_p,q is trivially in P since a graph G is (p,q)-mixing if and only if G has no edges. 
  
  Our characterization of (p,q)-mixing builds on the following characterization of (p,q)-colouring reconfiguration.  Given a (p,q)-colouring f of G,  a vertex v is fixed under f if for all (p,q)-colourings g to which f reconfigures, we have g(v) = f(v).  
  
  
  Fix p,q ∈ℕ such that 2 ≤p/q <4. Let G be a graph and let f, g be two (p,q)-colourings of G. Then f reconfigures to g if and only if the following three conditions are satisfied:
  
  
  
    * For all vertices v ∈ V(G), if v is fixed under f, then v is fixed under g. Furthermore, for all fixed vertices v, we have f(v) = g(v).
  
  
    * For all cycles C in G, W(C,f) = W(C,g).
  
  
    * For all paths P in G whose endpoints are fixed, W(P,f) = W(P,g).
  
  
  
  Thus, to certify that G is not (p,q)-mixing, it suffices to find two colourings that violate one of the three conditions above.  However, we now show for the mixing problem this reduces to checking the weight of cycles.
  Indeed if G admits a (p,q)-colouring f with fixed vertices, then G is not (p,q)-mixing. To see this, suppose v is a fixed vertex under f. Define g such that for all x ∈ V(G), g(x) = (f(x) +1)  p. Then g is a (p,q)-colouring, since for any edge xy ∈ E(G), we have |g(x) -g(y)| = |f(x)-f(y)|.  As f(v) ≠ g(v), f does not reconfigure to g.  
  
  We now show that the existence of fixed vertices under some colouring f implies the existence of two colourings and a cycle C on which the colourings have different weights. 
  
  Given a graph G and a (p,q)-colouring f, a vertex v ∈ V(G) is locked if for all (p,q)-colourings g which are adjacent to f in (G,G_p,q) satisfy f(v) = g(v). (That is, v cannot change colour until some other vertex does first.)
  
  
  
  Let 2 < p/q < 4.  Suppose G is a graph and f is a (p,q)-colouring of G. Then a vertex v is locked if and only if there exist vertices u, w ∈ N(v) such that W(uv,f)=W(vw,f)=q or W(uv,f)=W(vw,f)=p-q.
  
  
  
  
  Let 2 < p/q < 4. Given a graph G and a (p,q)-colouring f of G, suppose that c_0 is a fixed vertex under f. Then there exists a cycle C, V(C) = c_0, c_1, …,c _l-1, c_0 such that W(c_i c_i+1,f) = q for each i or W(c_i c_i+1,f) = p-q for each i. Here the subscripts on the vertices are taken modulo l.  
   
  
  Whereas, fixed vertices play a crucial role in the the G_p,q problem, we now show that, for 2 < p/q <4, testing if G is (p,q)-mixing reduces to the single condition of checking the wind of cycles. 
  
  
  
  Let 2< p/q <4 and G be a graph. The graph G is not (p,q)-mixing if and only if 
  there is a cycle C in G and two colourings f and g where W(C,f) ≠ W(C,g). 
  
  
  
  
  If there are two colourings f and g where W(C,f) ≠ W(C,g), 
  then by Theorem <ref> f does not reconfigure to g and thus 
  G is not (p,q)-mixing.
  
  Now suppose G is not (p,q)-mixing. Suppose f and f' are in different 
  components of (G,G_p,q). If neither f or f' has fixed vertices, 
  then by Theorem <ref> there is a cycle C such that 
  W(C,f) ≠ W(C,f'). Therefore without loss of generality f has a fixed vertex. 
  By Corollary <ref> we can find a 
  cycle C = c_0, c_1, … c_l-1, c_0 such that W(c_i c_i+1, f) = q 
  for all i or W(c_i c_i+1, f) = p-q for all i.  
  Assume the former holds (the latter is analogous).  Thus, W(C,f) = q|E(C)|. Define a 
  (p,q)-colouring g by g(v) = p-f(v) for all v ∈ V(G). (If f(v) = 0, then g(v) = p
  and we reduce g(v) p so that g(v) = 0.)
  This is a (p,q)-colouring, since for any edge uv ∈ E(G),  
  we have |g(v) - g(u)| = |p- f(v) - p + f(u)| = |f(u) - f(v)|. 
  (In the case f(v)=g(v)=0, a similar analysis verifies g(u)g(v) is an edge of G_p,q.)
  In particular W(c_i c_i+1, g) = p-q for all i as -q p = p-q.
  Therefore W(C,g) = (p-q)|E(C)|.  Since p/q≠ 2, W(C,g) ≠ W(C,f).
  
  
  We now state our characterization for (p,q)-mixing.
  
  
  
  Fix 2 < p/q < 4 and let G be a graph. Then G is not (p,q)-mixing if and only 
  if there exists a (p,q)-colouring f of G and a cycle C in G where 
  W(C,f) ≠|E(C)|/2p.
  
  
  
  If G is not (p,q)-mixing, then by Lemma <ref> 
  there exist (p,q)-colourings f and g, and a cycle C such that 
  W(C,f) ≠ W(C,g). Then at most one of W(C,f) or 
  W(C,g) equals |E(C)|/2p, so the result follows.
  
  Conversely, assume that we have a (p,q)-colouring f and cycle 
  C=c_0, c_1, …, c_l, c_0 where W(C,f) ≠|E(C)|/2p. 
  Consider the (p,q)-colouring g where g(v) = p -f(v) for all v ∈ V(G)
  (with g(v)=0 when f(v)=0). Then W(c_i c_i+1,g) = p - W(c_i c_i+1,f).
  Thus, W(C,g) = |E(C)|p - W(C,f).  
  Since W(C,f) ≠|E(C)|/2p, we have 
  W(C,g) ≠ W(C,f) and thus G is not (p,q)-mixing.
  
  
  The following is immediate.
  
  The G_p,q problem is in co-NP when 2 ≤p/q <4. 
  
  
  It follows from Theorem <ref> that if a graph G is (p,q)-mixing, then G is bipartite. This observation had already been made in <cit.>. In fact, they proved a stronger statement which we need some definitions to state. Define the circular mixing number as 
      m_c(G) = inf{p/q |  G  is  G_p,q-mixing}.
   Let ω(G) be the clique number of G, that is the number of vertices in the largest clique of G. 
  
  
  
  Let G be a non-bipartite graph. Then m_c(G) ≥max{4, ω(G) +1}. 
  
  
  As we are interested in (p,q)-mixing when 2 < p/q < 4, we will restrict our attention to bipartite graphs from now on.
  
  
  Let f be a (p,q)-colouring of G. For any cycle C of G, if W(C,f) ≠|E(C)|/2p, then we say that C is wrapped under f. To explain this choice of terminology, consider a C = c_0,c_1,…,c_2l-1, c_0 and a colouring f where W(C,f) ≠|E(C)|/2p.  The colouring g defined by g(c_i)=0 for i even and g(c_i)=q for i odd has g(C) = 0q, a single edge, and W(C,g) = |E(C)|/2p.  Hence f does not reconfigure to g.  Consequently, any colouring to which f reconfigures must have a cycle (of G_p,q) in its image (of C), i.e. any colouring to which f reconfigures must wrap C around a cycle of G_p,q.  Alternatively, a colouring of a cycle can be reconfigured to a colouring where the image is a single edge if and only if the cycle is not wrapped.  Thus, even cycles may or may not be wrapped but odd cycles are always wrapped.
  
  We complete this section with a final winding number result. 
  The sum of two cycles C_1 and C_2 is the graph induced by the edges of the 
  symmetric difference E(C_1)  E(C_2). Given a wrapped cycle
  that is the sum of two other cycles, then one of the two cycles is also wrapped. 
  Consequently, given a wrapped cycle, we can find a chordless cycle that is wrapped.
  
  
  
  Let G be a graph and f a (p,q)-colouring of G. 
  Let C=c_0, c_1, …, c_l, c_0 be a cycle which is wrapped under f. 
  Let P=p_0, p_1, …, p_k be a path whose endpoints 
  lie on C, i.e. p_0 = c_s and p_k = c_t, and whose internal vertices do not lie on C. 
  Then either C'=c_s, c_s+1, …, c_t-1, c_t, p_k-1, …, p_1, c_s or 
  C”=c_s, p_1, …, p_k-1, c_t, c_t+1, …, c_s-1, c_s is wrapped under f.
  
  
  
  Observe W(C',f) + W(C”,f) = W(C,f) + ∑_i=1^k (W(p_i-1p_i,f) + W(p_ip_i-1,f)) = W(C,f)+ kp. The reduction of the summation follows from Observation <ref>. Since |E(C')| = t-s+k and |E(C”)|=l-t+s+k, if neither is wrapped, then W(C',f) + W(C”,f) = (t-s+k)p/2 + (l-t+s+k)p/2 = lp/2 + kp. This implies W(C,f)= lp/2, i.e. C is not wrapped.  The result follows.
  
  
  
  
  
  
  
  § MIXING AND THE FOLDING OPERATION
  
  
  In this section we prove Theorem <ref>. For ease, we recall the definition of folding. Given a graph G, and two vertices x and y at distance 2, let G_xy be the graph obtained by identifying x and y and call the new vertex v_xy.  The homomorphism f: G → G_xy defined by f(x) = f(y) = v_xy and f(u)=u for u ∉{x,y} is an elementary fold. We say a graph G folds to a graph H if there is a homomorphism f: G → H where f is a composition of elementary folds and f(G) is isomorphic to H. We call such a mapping a folding. For brevity, we may refer to an elementary fold as just a fold.
  
  
  
   §.§ (𝐩,𝐪)-mixing is closed under folding
   
  
  
  
  
  Let H be a graph which is not (p,q)-mixing where 2 < p/q <4. If G folds to H, 
  then G is not (p,q)-mixing. 
  
  
  
  
  It suffices to prove the statement for a single elementary fold.  Suppose f: G → G_xy 
  is an elementary fold and G_xy is not (p,q)-mixing.  Then by Theorem <ref> 
  there is a (p,q)-colouring of G_xy, ψ, and a cycle C = v_0,v_1,…,v_t,v_0 
  such that C is wrapped under ψ.  The homomorphism ψ' = ψ∘ f 
  is a (p,q)-colouring of G.  We will show there is a cycle C' in G that is 
  wrapped under ψ'.
  
  Let v_xy be the vertex formed by the identification of x and y under f.  
  If v_xy∉V(C), then C is a cycle of G and is wrapped under ψ' as 
  ψ = ψ' on C.  
  
  Thus, assume without loss of generality v_xy = v_1.  In G, if either v_0, v_2 ∈ N(x) 
  or v_0, v_2 ∈ N(y), then with a slight abuse of notation C belongs to G and is wrapped 
  under ψ'.  Otherwise, consider a common neighbour of x and y, say a.  
  By Lemma <ref>, we may assume C is an induced cycle of
  G_xy which implies (without loss of generality) the cycle 
  C': v_0, x, a, y, v_2, v_3, …, v_t, v_0 is a cycle of G. Since 
  ψ'(x) = ψ'(y) = ψ(v_xy) we have by Observation <ref>,
  
  
      W(xa,ψ') + W(ay,ψ') = (ψ'(a) - ψ'(x))  p + (ψ'(y) - ψ'(a))  p = p.
  
  Hence,
  
      W(C',ψ')    = W(C,ψ)+ W(xa,ψ')+W(ay,ψ') 
          = W(C,ψ) + p 
         ≠|E(C)|/2p + p 
          = |E(C')|/2p.
  
  The result follows.
  
  
  
  
  
   §.§ 𝐂_2𝐤+1-Mixing and Folds
  
  In this subsection, we show that for bipartite graphs G, 
  G is C_2k+1-mixing if and only if G 
  does not fold to C_4k+2.  First we characterize which cycles are C_2k+1-mixing.
  
  [<cit.>]
  
  The cycle C_4 is (p,q)-mixing for all p/q >2. 
  
  
  
  
  For r ≥ 3, the even cycle C_2r is C_2k+1-mixing for all r ≤ 2k.
  
  
  
  
  The even (respectively odd) cycle C_2k (C_2k+1) folds to all even (odd) cycles 
  C_2k' (C_2k'+1) for 2 ≤ k' ≤ k.
  
  
  
  Suppose the cycle is v_0, v_1, v_2, v_3, …, v_t, v_0.  Identify v_0 and v_2, and 
  then v_1 and v_3. The result is a cycle with two fewer vertices, and so by induction 
  the result follows.
  
  
  Combining these results we obtain the following.
  
  
  
  Fix an integer k ≥ 1. Then C_2r is C_2k+1-mixing if and only if r ≤ 2k.
  
  
  
  If r ≤ 2k, then the observation follows from Proposition <ref> for cycles larger than C_4, and follows from Observation <ref> for 4-cycles.
  
  If r ≥ 2k+1,  let C_4k+2 = c_0,…,c_4k+1,c_0. 
  The C_2k+1-colouring f(c_i) = ik 2k+1 has W(C_4k+2,f) = (4k+2)(k) ≠ (2k+1)(2k+1) and hence the cycle is wrapped.  Therefore C_4k+2 is not C_2k+1-mixing, and the result follows from Lemma <ref>.
  
  
  
  The above observation tells us that C_4k+2 is the minimum even cycle which is not 
  C_2k+1-mixing. It turns out, C_4k+2 is the unique minimal (with respect to folding) 
  bipartite graph which is not C_2k+1-mixing.
  
  
  
  A connected bipartite graph G is not C_2k+1-mixing if and only if G folds to C_4k+2.
  
  
  
  If G folds to C_4k+2, then the claim follows from Lemma <ref> 
  and Observation <ref>.
  
  To prove the converse, suppose G is a vertex minimal counter-example.  That is, G is not 
  C_2k+1-mixing, but does not fold to C_4k+2.  By Theorem <ref>, we may 
  assume there is a C_2k+1-colouring ψ of G and C a cycle of G that is wrapped 
  under ψ.  By Observations <ref> and <ref> we may assume that 
  G is not a cycle.
  
  First, if there exist three consecutive vertices x,y,z ∈ V(C) such that ψ(x) = ψ(z), 
  then xz ∉E(G) and we fold x and z to create the vertex v_xz. 
  Call the resulting graph G_xz and the resulting cycle C'. The map ψ induces a 
  colouring ψ': G_xz→ C_2k+1 by
  
      ψ'(w) = {ψ(x)     w = v_xz
      ψ(w)    .
  
  Let P' be the path in C from z to x not using y, and P” be the path x,y,z. Then W(C,ψ) = W(P”,ψ) + W(P',ψ). We have that  W(P”,ψ) = p by Observation <ref>.  Finally, W(P',ψ) = W(C',ψ') by construction.  Thus, W(C',ψ') = W(C,ψ) - p, E(C') = E(C)-2 and hence W(C',ψ') ≠ |E(C')|p/2 and C' is wrapped under ψ'. By minimality G_xz folds to C_4k+2 and thus G folds to C_4k+2, a contradiction.
  
  Hence assume three such vertices do not exist. Since G is connected, but not a cycle, there is a vertex a ∈ V(G) ∖ V(C) adjacent to a vertex, say y ∈ V(C).  Let x and z be the neighbours of y in C. Observe that the vertex ψ(y) is a vertex of the cycle C_2k+1. As C_2k+1 is 2-regular and ψ(x) ≠ψ(z), ψ(x) and ψ(z) are the two distinct neighbours of ψ(y). As ψ(a) is also a neighbour of ψ(y), it follows that either ψ(a) = ψ(x) or ψ(a) = ψ(z). Without loss of generality we assume  ψ(a) = ψ(x).  
  Let f be the fold identifying a and x to form G_ax.  The cycle C is (still) 
  wrapped under the C_2k+1-colouring ψ∘ f of G_ax.  Consequently 
  G_ax is not C_2k+1-mixing. By minimality, G_ax folds to C_4k+2 and thus G folds to C_4k+2, a contradiction.
  
  
  Note that the folding operation cannot reduce the number of connected components in a graph.  
  (Vertices from different components cannot be identified.)  Since a graph is C_2k+1-mixing 
  if and only if each connected component is C_2k+1-mixing, we can remove the connected 
  condition in the theorem and simply require that at least one component folds to C_4k+2.
  
  We now examine foldings of non-bipartite graphs.  Using the above proof we construct a partial extension to circular colourings of the following theorem of Cook and Evans.
  
  
  Let G be a connected graph. If χ(G) = k, then G folds to K_k. 
  Furthermore, any graph that folds to K_k is k-colourable.
  
  
  One might conjecture that if χ_c(G) = p/q, and G is connected, then G folds to G_p,q. Unfortunately, this is not the case, due to a theorem of Zhu <cit.>. 
  
  
  Fix integers p,q such that p ≠ 2q+1 and q ≠ 1. Then there exists a graph G such that G is a strict subgraph of G_p,q, and χ_c(G) = p/q. 
  
  
  
  As a strict subgraph of G_p,q cannot possibly fold to G_p,q we see that the natural conjecture is false.  As <cit.> affirms G does fold to the clique that determines its chromatic number, the result of Zhu does leave open the possibility that G folds to the odd cycle G_2k+1,k when χ_c(G) = 2k+1/k.  We now prove this is the case.
  
  
  
  We note that the hypothesis  in Theorem <ref> requiring the graph to be bipartite is used only to determine the shortest cycle to which G can fold and not be C_2k+1-mixing.  In fact, 
  the proof of Theorem <ref> shows for any graph G,  if G admits a 
  C_2k+1-colouring ψ and contains a wrapped cycle C under ψ, 
  then G folds to some cycle C' (and C' admits a C_2k+1-colouring).    
  In particular, if G is not bipartite (and thus G has a wrapped cycle under any ψ), then  
  G folds to an odd cycle C' and C' has length at least 2k+1. Hence we have the following lemma.
  
  
  
  Let k ≥ 1 be an integer.  Suppose G is a connected, non-bipartite graph and has a C_2k+1-colouring. Then G folds to C_2k+1. 
  
  
  
   
  
  Let G be a connected graph. If χ_c(G) = 2k+1/k, then G folds to C_2k+1. 
  Furthermore, any graph which folds to C_2k+1 is C_2k+1-colourable.
  
  
  
  Suppose χ_c(G) = 2k+1/k. Then G is not bipartite, and hence Theorem <ref> implies that G is not C_2k+1-mixing, as 4 > 2k+1/k. 
  By Lemma <ref>, G folds to C_2k+1. To see the second claim, 
  observe that elementary folds are homomorphisms and homomorphisms compose.  
  
  
  Combining the above discussion gives the following result.
  
  If q = 1 or p = 2q+1, then every connected graph G with χ_c(G) = p/q folds to G_p,q. For all other pairs (p,q), there exists a connected graph G with χ_c(G) = p/q that does not fold to G_p,q. 
  
  
  
   We finish this subsection by showing that Theorem <ref> that the circular mixing number of bipartite graphs is 2 as conjectured in <cit.>.
  
  
  For every connected, bipartite graph G, there exists a k_0 such that for every k ≥ k_0, G is C_2k+1-mixing.
  
  
  
  Let C be a largest cycle in G. Pick k_0 such that 4k_0+2>|V(C)| and k ≥ k_0. By Lemma <ref>, we know that G is not C_2k+1-mixing if and only if G folds to C_4k+2. Consider any cycle of G and any elementary folding applied to G.  Then the length of the cycle remains the same or is reduced by 2.  Consequently, folding G produces a graph where all cycles have length strictly less than 4k_0+2.  In particular, G cannot fold to C_4k+2.  Therefore, G is C_2k+1-mixing.
  
  
  Note that the choice of k_0 given in the above proof is tight, and can be seen by considering C_4k+2. Since 2k+1/k tends to 2 as k approaches infinity, we have:
  
  
  If G is bipartite, then m_c(G) =2.
  
  
  Combining this with Theorem <ref> we conclude:
  
  
  
  If G is bipartite, then m_c(G)=2. Otherwise, m_c(G) ≥max{4,ω(G)+1}.
  
  
  
  
  
   §.§ Showing that odd cycle mixing is co-NP-complete
  
  
  
  In this subsection we show the problem of determining whether an input graph G folds
  to the cycle C_2k, denoted as the C_2k problem, is NP-complete.
  For our reduction we require two additional homomorphism problems.   
  
  
  Let G be a graph and H an induced subgraph of G. A retraction of G to H is a 
  homomorphism r: G → H such that r(h) =h for every vertex h ∈ V(H). 
  If there exists a retraction of G to H, we say G retracts to H.
  
  
  The H problem takes as input a graph G containing a labelled subgraph isomorphic to H.
  It asks if there is a retraction of G to the copy of H in G.  We will give a reduction 
  from C_2k, which is known to be NP-complete for all k ≥ 3 
  (proven independently by Feder, and by Dukes, Emerson, and MacGillivray, see <cit.>), 
  to the C_2k problem. 
  
  An easy observation is that for connected graphs, a retraction is a fold.  (Consider a vertex
  v at distance one from H.  The image of v under the retraction is at distance two from v.) 
  Thus, we have the following.
  
  [<cit.>] 
  
  Let G be a connected graph, and H an induced subgraph of G. If G retracts to H, 
  then G folds to H.
  
  
  We also require a theorem of Vikas <cit.> relating retractions and compactions. 
  
  
  
  A compaction of G to H is a homomorphism G → H that is onto
  V(H) and onto all non-loops of E(H).  We say G compacts to H.
  
  
  The problem H takes an input graph G and asks if there is a compaction of
  G to H. It is easy to see for graphs without isolated vertices, a homomorphism that is edge surjective
  is also vertex surjective.  Additionally for irreflexive graphs the homomorphism f: G → H is a 
  compaction if and only if f(G) = H.
  
  
  
  
  Suppose G and H are irreflexive graphs.
  Let f:G → H be a folding. Then f is a compaction of G to H. 
  
  
  
  By definition of a folding, f(G) = H making f both vertex and edge surjective.
  
  
  
  In the proof that C_2k-compaction is NP-complete for all 
  k ≥ 3, Vikas proves the following:
  
  
  
  Let G be a graph with an induced copy of C_2k, k ≥ 3. 
  Then there is a graph G' such that the following are equivalent:
  
  
  
    * G retracts to C_2k,
  
    * G' retracts to C_2k,
  
    * G' compacts to C_2k.
  
  
  
  We make two comments about the above theorem.  First,
  the graph G' in the above theorem depends on the value of k. 
  Secondly, using the following observation, we may restrict our attention 
  in the C_2k problem to connected graphs G.
   
  
  
  Let G be a graph containing a labelled copy of C_2k as an induced subgraph of G. 
  Then G retracts to the copy of C_2k if and only if the connected component containing 
  C_2k retracts to C_2k and all connected components are bipartite.
  
  
  
  The necessary condition is obvious. Conversely, mapping all connected components not containing 
  C_2k to an edge of C_2k (which is possible since they are bipartite) and using the 
  retraction of the connected component containing C_2k gives a retraction of G to
  the labelled copy of C_2k. 
  
  
  In Vikas's proof of Theorem <ref>, the graph G' is constructed from 
  G by adding paths (whose lengths depend on k).  Thus, if G is connected,
  then we can conclude G' is connected as well.  Further, the construction
  will produce a bipartite graph G' when G is bipartite.
  Therefore we can strengthen Vikas's result to the following:
  
  
  Let G be a connected graph with an induced copy of C_2k, k ≥ 3. 
  Then there is a connected graph G' such that the following are equivalent:
  
  
  
    * G retracts to C_2k,
  
  
    * G' retracts to C_2k,
  
  
    * G' folds to C_2k,
  
  
    * G' compacts to C_2k.
  
  
  
  
  First assume G' retracts to C_2k.  By Observation <ref>, 
  since G' retracts to C_2k and G' is connected, G' folds to C_2k. 
  Now assume that G' folds to C_2k. Then by Observation <ref>, 
  G' compacts to C_2k. By Theorem <ref>, the result follows. 
  
  
  We now prove our main result for this section:
  
  
  
  For a fixed k ≥ 1, C_2k+1 is co-NP-complete.
  
  
  
  Let G be an instance of C_4k+2. Then we may assume G is bipartite. 
  Further by Observation <ref>, we may assume G is connected.  
  By Theorem <ref>, there is a connected, bipartite graph G' that folds 
  to C_4k+2 if and only if G retracts to C_4k+2.  Thus, by Theorem <ref> 
  we have G' is no instance of C_4k+2 if and only if G is a yes instance of
  C_4k+2.  The result follows.
  
  
  
  
  
  
  § (P,Q)-MIXING IN PLANAR GRAPHS
  
  
  Now we turn our attention to (p,q)-mixing in planar graphs. In <cit.>, 
  Cereceda et al. showed that there is a polynomial time algorithm to determine 
  if a graph is 3-mixing when restricted to planar (bipartite) graphs. 
  Here we extend the result by giving a polynomial time algorithm for determining if
  a bipartite planar graph is (p,q)-mixing for 
  3 ≤p/q < 4.  In <cit.>, the key ideas for the polynomial algorithm are as follows.  For k=3, C_4 is 3-mixing and C_6 is not.  Let G be a 2-connected, bipartite graph with a planar embedding.  If G has a separating C_4, then G can be decomposed into two subgraphs such that G is 3-mixing if and only if both subgraphs are.  If G has no separating C_4, then G is 3-mixing if and only if G has at most one face of length at least 6.  In extending the results to general 2 < p/q < 4, we need to both understand what a large face is and how to decompose using short separating cycles. 
  
  Our following structural result characterizes (p,q)-mixing for bipartite graphs with planar embeddings not containing short separating cycles.  As in <cit.>, the polynomial algorithm follows from the characterization together with a reduction of the general case to the case without short separating cycles.  
  Our structural result applies to all 2 < p/q < 4 without small separating cycles, but the reduction to remove separating cycles as in <cit.>, requires 3 ≤p/q < 4 where the short separating cycles are precisely C_4.  Hence our algorithm applies only to 3 ≤p/q < 4.
  
  As a notation convention, in this section given an embedding of a planar graph G we will use G to denote both the graph and its embedding.
  
  
  Fix 2 < p/q < 4. Let C_2k be the minimal non-(p,q)-mixing even cycle. Let G be a 2-connected bipartite planar graph.  Suppose G has a planar embedding with no separating C_2i-cycles for i ∈{2,…,k-1}. Then G is (p,q)-mixing if and only if G has at most one face with length greater than or equal to 2k. 
  
  
  Our first point of order is to show that the minimal even cycle which is not (p,q)-mixing is well defined.
  
  
  Fix integers p and q such that 2 < p/q < 4. If p is even, then for all even integers j ≥ p,  C_j is not (p,q)-mixing. If p is odd, then for all even j ≥ 2p,  C_j is not (p,q)-mixing.
  
  
  
  First assume that p is even. Let C_p = c_0,…,c_p-1,c_0 and consider the 
  (p,q)-colouring f(c_i) = iq p, i=0, 1, …, p-1. Then W(C,f) = qp < p/2p as p/q >2. Hence C_p is not (p,q)-mixing. It follows by Lemma <ref> that when p is even, for all even j  ≥ p, C_j is not (p,q)-mixing.
  
  Now assume that p is odd. Let C_2p = c_0,…,c_2p-1,c_0. For i = 0, 1, …,p-1, colour c_i and c_i+p with iq  p. Again, W(C,f) = 2qp < p^2, and thus C_2p is not (p,q)-mixing. Hence, for all even j ≥ 2p, C_j is not (p,q)-mixing. 
  
  
  It follows that the minimal even cycle which is not (p,q)-mixing is well defined. In fact, the minimum can be found in fixed time (for fixed p and q), as we only have a fixed number of cycles which we need to check and we can check if a single cycle is (p,q)-mixing in fixed time. 
   
  First, we reduce the problem G_p,q problem to 2-connected graphs. 
  
  
  Fix integers p and q such that 2 < p/q < 4.  Let G be a graph with a (p,q)-colouring.  Then G is (p,q)-mixing if and only if every block of G is (p,q)-mixing.
  
  
  
  Suppose that a block B of G is not (p,q)-mixing. Then there is a (p,q)-colouring f of B such that some cycle C in B is wrapped under f. Observe that we can extend f to a (p,q)-colouring of G by taking (p,q)-colourings of each block (which exist as G has a (p,q)-colouring), and permuting colours if necessary. 
  
  Conversely, suppose that G is not (p,q)-mixing. Then there is a (p,q)-colouring f of G and a cycle C in G which is wrapped under f. As a cycle is 2-connected, C lies in some block B. Then f restricted to B is a (p,q)-colouring which has a wrapped cycle, and hence B is not (p,q)-mixing. 
  
  
  Therefore, we can assume for the remainder of this section that all graphs are 2-connected. Recall that if a planar graph is 2-connected, then every face is bounded by a cycle.  The next observation allows us to assume G does not have a clique cutset of size two.
  
   
  
  
  Fix integers p and q such that 2 < p/q < 4. Let G be a 2-connected graph, and suppose uv ∈ E(G) such that G ∖{u, v} is disconnected with components T_1, T_2, …, T_k. Let G_1 and G_2 be induced subgraphs of G such that V(G_1) = V(T_1) ∪{u,v},  V(G_2) = V(T_2) ∪⋯∪ V(T_k) ∪{u,v}, and E(G_1) ∪ E(G_2) = E(G). If G_1 and G_2 are (p,q)-mixing, then G is (p,q)-mixing.
  
  
  
  Suppose to the contrary G is not (p,q)-mixing. Then there is a (p,q)-colouring f of G and a cycle C such that C is wrapped under f. As G_1 and G_2 are (p,q)-mixing, this implies that V(C) ⊈V(G_1) and V(C) ⊈V(G_2). In particular, u,v ∈ V(C) and uv ∉E(C). Let C_1 be the (u,v)-path of C in G_1, and C_2 be the (v,u)-path of C in G_2. Then C_1 +uv and C_2 + vu are cycles, and by Lemma <ref> at least one of them is wrapped under f. But this contradicts the assumption that G_1 and G_2 are (p,q)-mixing.
  
   
  
  We now prove the necessity of the condition in Theorem <ref>.  Note we for this direction the absence of small separating cycles is not required.
  We say a ≥ k-face is a face whose boundary has at least k edges. 
  
   
  
  Fix 2 < p/q <4. Let C_2k be the minimal even cycle which is not (p,q)-mixing. Let G be a 2-connected planar bipartite graph. Suppose G has a planar embedding in which there is at most one ≥ 2k-face. Then G is (p,q)-mixing. 
  
   
   
  Let G be an edge minimal counterexample to the claim. If G is a cycle, then the inner face and outer face of the cycle are both faces of length equal to that of the cycle.  Hence, the cycle has length strictly less than 2k (there is at most one ≥ 2k-face), and G is (p,q)-mixing.  Thus, we assume that G is not isomorphic to a cycle.
  
  If one exists, let f be the ≥ 2k-face, otherwise let f be an arbitrary face, and let C = v_0,…,v_t-1,v_0 be the facial cycle of f.  Without loss of generality, let f be the outer face. Thus, all faces in the interior of C have length less than 2k. If C has a chord, then this chord lies in the interior of C, and we have  a clique cutset of size two which decomposes G into two graphs G_1 and G_2, each of which only has at most one ≥ 2k-face, since all interior faces have length strictly less than 2k. By minimality both G_1 and G_2 are (p,q)-mixing, which by Observation <ref> implies G is (p,q)-mixing.
  
  
  
  
  There exists a face f', where f' has a facial cycle C' such that V(C') ∩ V(C) induces a path of length at least 1. 
  
  
  
  
  Pick an arbitrary edge e= v_jv_j+1∈ E(C). Let f' and f be the two distinct faces whose boundaries contain e. Let C' be the facial cycle of f'. 
  We now examine the induced subgraph G[V(C) ∩ V(C')].  If it contains an edge not in C (but whose endpoints are necessarily in C), then C has a chord.  Thus, all edges belong to C.  Moreover, the subgraph cannot be all of C, otherwise f' is the interior of C and G is a cycle. We may assume that G[V(C) ∩ V(C')] is a union of paths.  If it is a single path, then we are done, so assume there is more than one path.  Let P be the component containing v_j and let v be an endpoint of P.  Let Q' be the path in C' starting at v and ending at a vertex u ∈ V(C) such that V(Q') ∩ V(P) = {v}, and all internal vertices of Q' are not in V(C). Similarly, let Q be the path in C from u to v whose internal vertices are not in V(C').  In particular, Q and P share only the vertex v.  Now Q' ∪ Q is a cycle C” intersecting C in the path Q.  If C” is facial, then we are done. Otherwise, Q shares an edge with f and a face f” in the interior of C”.  We repeat the argument.  As G is finite, the result follows.
  
  
   
    
  Let e be on the boundary of a face f', with facial cycle C', such that S = G[V(C) ∩ V(C')] is a path.  Let v' and v” be the endpoints of S and S' be the set of interior vertices. 
  
  Consider G' := G - S' - {e}. (The deletion of e is only required when S' = ∅.) Notice as all of the vertices of S are on the boundary of f, we do not create two ≥ 2k faces. We have two cases to consider.
  
  First suppose G' is 2-connected. Since G is an edge minimal counterexample, G' is (p,q)-mixing. Now consider any (p,q)-colouring ϕ of G. Observe that ϕ restricts to a (p,q)-colouring of G'. As G' is (p,q)-mixing, for all cycles D in G', we have W(D,ϕ) = |E(D)|/2p. It suffices to show that the winds of C' and C are |E(C')|/2 and |E(C)|/2 respectively.  As |E(C')| < 2k, we have W(C',ϕ) = |E(C')|/2p. So it suffices to show that W(C,ϕ) = |E(C)|/2p. To see this, consider the cycle C” := C Δ C'. Then since W(C”,ϕ) = |E(C”)|/2p and W(C',ϕ) = |E(C')|/2p, by Lemma <ref> it follows that W(C,ϕ) = |E(C)|/2p. 
  
  
   Otherwise, G' has a cut vertex v. We are going to argue that this cannot occur. Let T_1,T_2,…,T_t be the components of G' - v. We claim that t=2. As v is a cut vertex, by definition t ≥ 2. By construction, all vertices in S' have degree 2 in G. Adding the path S to G' joins at most two of the components in G' -v. Therefore if t ≥ 3, G contains a cut vertex, a contradiction. 
   
   Thus, we can decompose G' into two graphs G_1 and G_2, such that V(G_1) ∩ V(G_2) = {v},  both G_1 and G_2 contain at least two vertices, and up to relabelling, v' ∈ V(G_1), v”∈ V(G_2). 
   
   First suppose that v = v'. Then as G' is simply G with S' and e deleted, there is a vertex x ∈ V(G_1) ∖{ v'} such that every path from x to v” contains v'. But this implies that G is not 2-connected, a contradiction. By a similar argument, we can assume that v ≠ v”.
  
  Now we can conclude that all paths from v' to v” in G' must have v as an internal vertex.  In particular, the path from v” to v' in C-S'-{ e } must contain v.  We conclude v ∈ V(C).  The boundary of f' contains a path from v' to v” that does not use S' ∪{ e }.  In particular, this path must contain v.  We conclude v ∈ V(C) ∩ V(C') contrary to our assumption that V(C) ∩ V(C') is the path S which establishes the lemma.
  
  
  We now prove the sufficiency of the condition in Theorem <ref>. We begin with some observations used in the proof.
  
  
  
  Let G be a planar graph, let x,y,z be consecutive vertices on a face, and suppose that d(x,z) =2. Then the graph obtained by folding x and z is planar. 
  
  
  One can see this by simply adding the edge xz inside the face and then contracting the edge. 
  
  The next lemma due to Hell is well known and follows from a simple breadth first search argument, see for example <cit.>.
  
  
  
  Let G be a connected bipartite graph, and let P be a shortest path from x to y in G. Then G retracts to P. 
  
  
  We state a useful and well known corollary of this fact.
  
  
  
  Let G be a connected bipartite graph, and C a shortest cycle in G. Then G retracts to C.
  
  
  Let e be any edge in C. Then G-e retracts to C-e by Lemma <ref>, and thus G retracts to C.
  
  
  Let G be a connected graph and C be a cycle in G. Given a planar embedding of G, following the notation of <cit.>, we let Int(C) and Ext(C) be the set of vertices inside and outside C respectively.  Neither of these sets include the vertices of C.  We define the interior of C, denoted G_int(C), to be the induced subgraph G[V(C) ∪Int(C)] and the exterior of C to be G_ext(C) = G[V(C) ∪Ext(C)].  The cycle C is separating if both Int(C) and Ext(C) are non-empty.
  We use the abbreviated notation G_int and G_ext when the cycle is clear from context.
  
  We now establish the sufficiency of Theorem <ref>.
  
  
  Fix 2 < p/q < 4. Let C_2k be the smallest even cycle which is not (p,q)-mixing. Let G be a 2-connected bipartite graph with a planar embedding containing no separating C_2i-cycle for all i ∈{2,…, k-1}. If G has at least two ≥ 2k-faces, then G is not (p,q)-mixing. 
  
  
  
  Let f, f_o be two ≥ 2k-faces, and suppose that the boundaries of f, and f_o, are C, and C_o, respectively. Without loss of generality, we may suppose that f_o is the outer face. 
  A cycle D is f-separating if f lies in G_int(D) and either D is a separating cycle or D=C_o, the boundary of the outer face.  In particular, C_o is f-separating despite the fact that C_o is not separating. As |E(C_o)| ≥ 2k and G has no separating cycles of length less than 2k, G has no f-separating cycles of length less than 2k.
    
  If G is a cycle, then G folds to C_2k and G is not (p,q)-mixing by Lemma <ref>.  Otherwise, we show that G folds to a bipartite graph G' on fewer vertices, such that G' contains a block with two ≥ 2k-faces, the face f (from G) and f'_o (the outerface of B'), and no f-separating cycle of length 2i, i ∈{ 2, …, k-1 }.  The result follows by induction.
    
  Therefore assume G is not a cycle and let y ∈ V(C) such that (y) ≥ 3.   
  
  Let z be a neighbour of y on C, and a be a neighbour of y not in C, such that all of a,y, and z lie on a face (such a choice of z and a exists). Fold a and z and let G' be the resulting graph. As a,y and z lie on a face of G, the graph G' is planar.  
  Moreover, f is still a face of G' as a ∉V(C). (We may think equivalently of G' as being formed by deleting a and joining z to all the neighbours of a.  As a ∈Ext(C) this process leaves the face f unchanged.)   Let B' be the block of G' containing f.  Now we consider two cases.
    
    
  Case 1: B' has no f-separating C_2i-cycle for i ∈{2,…,k-1}. 
  
  The outerface of B' is an f-separating cycle.  Thus, it has length at least 2k.  The outerface together with f are two ≥ 2k-faces of B'.  By induction, B' is not (p,q)-mixing from which we conclude G' is not (p,q)-mixing by Observation <ref>, and by Lemma <ref>, G is not (p,q)-mixing.
   
  Case 2: B' has an f-separating cycle D' of length less than 2k.
  
  Let v_az be the new vertex obtained from folding a and z.  As G has no f-separating cycle of length less than 2k, we have v_az∈ V(D').  Let v'_az and v”_az be the two neighbours of v_az in D'. Observe that without loss of generality, a is adjacent to v'_az and not to v”_az in G and z is adjacent to v”_az but not to v'_az in G, as otherwise, G has an f-separating cycle of length less than 2k. Let D be the cycle (in G) that gave rise to D' in B', i.e. D is the cycle obtained by replacing the path v'_az, v_az, v”_az in D' with the path v'_az, a, y, z, v”_az.  Since C is in G_int(D) and C_o is in G_ext(D), if |E(D)| < 2k, then G contains an f-separating cycle of length less than 2k, a contradiction.  Since D' has length less than 2k, it follows that |E(D)| = 2k and |E(D')| = 2k-2.
  
  We claim D is an f-separating cycle.  As |E(C)| ≥ 2k, |E(D)|=2k, and a ∈ V(D) \ V(C), there is a vertex of C in Int(D).  Thus, D is f-separating if there is a vertex in Ext(D) or D = C_o the boundary of the outerface.  Suppose neither holds. Since |E(C_o)| ≥ 2k and |E(D)| = 2k, it must be the case that V(C_o)= V(D).  Hence D must have a chord not belonging to C_o as D ≠ C_o.  However, this chord must be in the interior of D (as C_o bounds the outerface) which implies D is the sum of two shorter cycles one of which is f-separating, a contradiction.
  
  Let P be the path of length 2k-1 from y to z in D-zy.  We now claim that in G_int(D) - zy, the path P is a shortest (y,z)-path.  Suppose there is a shorter path P'.  Using the fact that D bounds the outerface of G_int(D) and zy is an edge of D, the cycle P'+zy is f-separating in G and of length less than 2k, a contradiction.
  Therefore, by Lemma <ref>, G_int (D)- zy retracts to P which implies G_int(D) folds to D. (The vertices y and z are fixed under the retraction.)  Let G” be the resulting graph from G after folding G_int(D) to D. In G”, D is the boundary of a ≥ 2k-face and the outerface is a ≥ 2k-face.  (This includes the possibility that G”=D is simply a cycle.) Now by induction the result follows.
  
  
  Together Lemma <ref> and Lemma <ref> establish Theorem <ref>.  Since the property of being (p,q)-mixing is independent of any particular planar embedding we use, the following corollary is immediate.  
  
  
  Fix 2 < p/q < 4 and let C_2k be the minimal non-(p,q)-mixing cycle.  Let G be a 2-connected, planar bipartite graph.  Then for all planar embedding of G with no separating C_2i-cycle, i ∈{ 2, …, k-1 }, either all such embeddings have at most one ≥ 2k-face, in which case G is (p,q)-mixing, or all such embeddings have at least two ≥ 2k-faces, in which case G is not (p,q)-mixing.
  
  
  Now we show we can perform reductions to remove small separating cycles. 
  The first result handles all short separating cycles.
  
  
  
  Fix 2 < p/q <4. Let C_2k be the smallest even cycle which is not (p,q)-mixing. Let G be a 2-connected planar bipartite graph.  Suppose G has a planar embedding where C is a separating C_2i-cycle, for some i ∈{ 2, …, k-1 }. If both G_1 = G_int(C) and G_2 = G_ext(C) are (p,q)-mixing, then G is (p,q)-mixing. 
  
  
  
  Suppose that G is not (p,q)-mixing. Let ϕ be a G_p,q-colouring where there is a wrapped cycle D. If D contains vertices from both G_1 and G_2, then D crosses the separating cycle C (note, D ≠ C since C is (p,q)-mixing). Then we can (repeatedly, if required) apply Lemma <ref> to obtain a wrapped cycle which lies completely in G_1 or G_2, and thus either G_1 or G_2 is not (p,q)-mixing.
  
  
  We give an example below to show the converse of Lemma <ref> does not hold for all 2 < p/q < 4.  Hence, we require a stronger assumption that G has a separating 4-cycle.
  
  
  
  Let G be a 2-connected planar bipartite graph, and suppose it has a planar embedding with a separating four cycle C. If either G_int(C) or G_ext(C) is not (p,q)-mixing, then G is not (p,q)-mixing.
  
  
  
  Without loss of generality assume G_int(C) is not (p,q)-mixing.
  By Corollary <ref>, G_ext(C) retracts to C. As every retract of a connected graph is a folding, this implies G folds to G_int(C), which is not (p,q)-mixing, and hence G is not (p,q)-mixing.
  
  
  We need one more observation before we can finish the polynomial time algorithm.  
  
  
  The graph C_6 is not (p,q)-mixing for any 3 ≤p/q <4.
  
  
  
  Let v_0,v_1,v_2,v_3,v_4,v_5 be the vertices of C_6, where v_iv_i+1∈ E(C_6) for i ∈{0,…,5}, indices taken modulo 6. Let f be the (p,q)-colouring where f(v_0) = f(v_3) = 0, f(v_1) = f(v_4) = q, f(v_2) = f(v_5) = 2q. This is a proper (p,q)-colouring as p/q≥ 3. Observe that |E(C)|/2p = 3p. Orienting C from v_i to v_i+1 for i ∈{0,…,5}, we have W(C,f) = 2p < 3p, and hence C_6 is not (p,q)-mixing. 
  
  
  
  Now it follows from the above sequence of claims that there is a polynomial time algorithm for determining if a bipartite planar graph is (p,q)-mixing when 3 ≤p/q <4, proving Theorem <ref>.
  
  To see this, one first finds a planar embedding. Secondly, find all two connected blocks of the graph. Thirdly, enumerate all separating 4-cycles and reduce to the case where there are no separating 4-cycles. Lastly, check if the resulting graphs are (p,q)-mixing by testing the size of the faces in the embedding. As p and q are fixed, each of these steps can be done in polynomial time (with the running time depending on p and q). To obtain a precise running time, one can do analysis similar to that in <cit.>.
  
  
  We finish by showing the need to restrict our reduction to separating four cycles in the last result is necessary. For (5,2)-mixing the shortest even cycle that is not mixing is C_10.  We now give an example of a 2-connected planar bipartite graph G with a planar embedding containing a separating 8-cycle C such that G_int(C) is not (5,2)-mixing but the entire graph G is (5,2)-mixing. We will use the following observation:
  
  
  
  Fix positive integers p,q such that 2 < p/q < 4. Let G be a connected graph, and u be a vertex whose neighbourhood is contained in the neighbourhood of a vertex v. Let G_uv be the graph obtained from folding u and v. Then G is (p,q)-mixing if and only if G_uv is (p,q)-mixing. 
  
  
  
  If G is (p,q)-mixing, then Lemma <ref> implies that G_uv is (p,q)-mixing.
  
  Now suppose that G is not (p,q)-mixing. Then there is a (p,q)-colouring f of G and a cycle C in G which is wrapped with respect to f. As the neighbourhood of u is contained in the neighbourhood of v, we may recolour u so that f(u) = f(v).  Since 2 < p/q < 4, such a recolouring does not change the weight of any cycle, and so C is still wrapped <cit.>.
  We define the (p,q)-colouring f' of G_uv by f'(x) = f(x) for all x ∈ V(G) ∖{u,v} and if x_uv is the vertex obtained from folding u and v, we let f'(x_uv) = f(v). That is,
  f = f' ∘ g where g is the fold that takes u to v.  Thus, W(C,f) = W(C,f' ∘ g).  Since g(C) is either a cycle in G_uv or two cycles sharing the vertex x_uv,  by a similar argument as given in Lemma <ref>, there is a wrapped cycle in G_uv, showing that G_uv is not (p,q)-mixing. 
  
  
  
  
  
  We construct our example G as follows. Let C be an 8-cycle with bipartition (A,B). Add a new vertex w adjacent to all vertices in A. Let u,v be two vertices in A where d(u,v) = 4 in C. Add a path P from u to v of new vertices such that P has length 6. Observe that G is planar. Consider the embedding where w lies on the exterior of C and P lies on the interior of C. Then G_int(C) is not (5,2)-mixing, since it has no separating i-cycle for i ∈{4,6,8} and two faces of length 10. Notice that each vertex of B has its neighbourhood in the neighbourhood of w.  Hence, we can fold each vertex of B to w.  Next we can fold each vertex of A ∖{ u, v } to u.  By repeatedly applying Observation <ref>, we see G is (5,2)-mixing if and only if C_8 is (5,2)-mixing, which is true.  See Figure <ref>.
  
  For p/q < 3, C_6 is (p,q)-mixing, so the shortest non-mixing cycle has length at least 8.  Using this, the example easily generalizes to any maximal mixing cycle C_2k by joining u and v with a path of length k+2 and adding w dominating one part (of the C_2k bipartition) so that the resulting graph folds to a cycle that is (p,q)-mixing.
  
  
  
  § CONCLUSION
  
  
  The study of K_3 and K_3 in <cit.> identifies several key ideas which extend to the study of G_p,q and G_p,q for 2 < p/q < 4.  While some of the results depend on p/q < 4, others depend on the homomorphism target being 2-regular or containing a triangle.  These notions all coincide for K_3, but differ for 2 < p/q < 4.  This paper represents an initial study into H in this finer landscape.  It will be interesting to develop further methods to provide a complete classification of the complexity of H for 2 < p/q < 4.
  
  
  
    
  
    plain
  
  
  
  