Hyobeen Kim
Kyungpook National University, Republic of Korea

Jae-baek Lee
University of Victoria, Canada

Mark Siggers
Kyungpook National University, Republic of Korea
The last author was supported by Korean NRF Basic Science Research Program (2015-R1D1A1A01057653) funded by the Korean government (MEST)
and the Kyungpook National University Research Fund.

Mixing for reflexive graphs]Mixing is hard for triangle-free reflexive graphs

[2010]Primary 05C15; Secondary 05C85

In the problem ${\rm Mix}(H)$ one is given a graph $G$ and must decide if the Hom-graph
${\rm {\bf Hom}}(G,H)$ is connected.  We show that if $H$ is a triangle-free reflexive graph with at least one cycle, ${\rm Mix}(H)$ is ${\rm coNP}$-complete.  The main part of this is a reduction to the problem ${\rm NonFlat}({\rm{\bf H}})$ for a simplicial complex ${\rm{\bf H}}$, in which one is given a simplicial complex ${\rm{\bf G}}$ and must decide if there are any simplicial maps $\phi$ from ${\rm{\bf G}}$ to ${\rm{\bf H}}$ under which some $1$-cycles of ${\rm{\bf G}}$ maps to homologically non-trivial cycle of ${\rm{\bf H}}$.  We show that for any reflexive graph $H$, if the clique complex ${\rm{\bf H}}$ of $H$ has a free, non-trivial homology group $H_1({\rm{\bf H}})$, then ${\rm NonFree}({\rm{\bf H}})$ is ${\rm NP}$-complete.

§ INTRODUCTION

In the last 15 years there have been several papers looking at the `recolouring' and `mixing' variations of the classical graph colouring, and the more general graph homomorphism, or $H$-colouring, problem.  These problems have a common presentation in terms of the `Hom-graph'.

A homomorphism $\phi:G \to H$ from a graph $G$ to a graph $H$ is an edge preserving vertex map. As a homomorphism from a graph $G$ to $K_k$ is a $k$-colouring of $G$, a homomorphism to $H$ is also called an $H$-colouring of $G$.  Given graphs $G$ and $H$, $\Hom(G,H)$ is the set of $H$-colourings of $G$. The $\Hom$-graph $\bHom(G,H)$ is the graph on the vertex set $\Hom(G,H)$
in which two vertices $\phi, \psi \in \Hom(G,H)$ are adjacent if for all edges $uv$ of $G$,
$\phi(u)\psi(v)$ is an edge of $H$.

While the well known $H$-colouring problem $\Hom(H)$ asks for an instance graph $G$ if the Hom-graph $\bHom(G,H)$ contains any vertices, one also has the following two natural variations.

The first variation is the problem of $H$-reconfiguration (or $H$-recolouring[The two problems, defined differently, coincide for graph, but not for digraphs. The distinction is addressed in [Brewster et al., 2021]).] which has attracted some interest lately [van den Heuvel, 2013]).

A graph $G$ and $f,g\in \Hom(G,H)$.
Is there a path in $\bHom(G,H)$ between $f$ and $g$?

The second variation is the problem of $H$-mixing, which is the main problem of this paper, and which has also been addressed lately [Cereceda et al., 2009, Brewster and Noel, 2015].

A graph $G$.
Is $\bHom(G,H)$ connected?

Homomorphisms, the Hom-graph, and the above problems can be defined for all relational structures, not just graphs, and it is well known ([Bulatov, 2017],[Zhuk, 2020]) that the problem $\Hom(H)$ is in $\NP$ for any finite structure $H$, and is either in $\Poly$ or is $\NP$-complete. The problems $\Recon(H)$ and $\Mix(H)$ are not known to be in $\NP$, but are in $\PSPACE$.  Indeed a path between homomorphisms can be verified one edge at a time in polynomial space, showing that $\Recon(H)$ is in $\PSPACE$ and observing that this can be done for every pair of homomorphisms shows that $\Mix(H)$ is also in $\PSPACE$.

In [Gopalan et al., 2009] the analogous problems were addressed for binary relational structures $H$. In this setting the $H$-reconfiguration problem was shown to exhibit dichotomy.  Depending on $H$, $\Recon(H)$ is either polynomial time solvable, or $\PSPACE$-complete. Once $\Recon(H)$ is known to by polynomial time solvable for a given structure $H$, the problem $\Mix(H)$ drops into the complexity class $\coNP$, as we now have a polynomial certificate of the disconnectedness of $\bHom(G,H)$.  In [Gopalan et al., 2009], the authors went on to conjecture a trichotomy for $\Mix(H)$ for binary relational structures $H$: depending on $H$, $\Mix(H)$ is polynomial time solvable, $\coNP$-complete, or $\PSPACE$-complete. They conjecture a classification for the trichotomy, and gave strong evidence supporting it.

The expectation is that with graphs $H$ we should have a similar complexity breakdown–
a dichotomy between $\Poly$ and $\PSPACE$-complete for $\Recon(H)$, and a trichotomy between $\Poly$, $\coNP$-complete, and $\PSPACE$-complete for $\Mix(H)$.  The graphs for which the problems are $\PSPACE$-complete should coincide. Though it seems premature to suggest a classification of the graphs $H$ for which these problems fall into the respective complexity classes, some discussion of this is given in [Lee et al., 2020] for $\Recon(H)$. The proofs in [Lee et al., 2020] and [Lee et al., 2021] are very topological, and suggest the topology of $H$ may play an important role in the complexity of $\Recon(H)$.  Indeed, the Hom-graph is was originated to apply topological ideas to graph colouring problems, so topological methods are perhaps inevitable.

There are few results about the complexity of mixing for graphs. Recall that a graph in which every vertex has a loop is reflexive and a graph in which no vertices have loops is irreflexive. For irreflexive graphs, it was shown in [Cereceda et al., 2009] that $\Mix(K_3)$ is $\coNP$-complete, and recently in [1] this was extended to all odd cycles.  Nothing yet has been proved for reflexive graphs, but there is one basic result from the literature. From [Brightwell and Winkler, 2000], we have that if a reflexive graph $H'$ dismantles to $H$, then $\bHom(G,H')$ has the same number of components as $\bHom(G,H)$ for all $G$. So the complexity of $\Mix(H')$ is the same as that of $\Mix(H)$.  From this we conclude  that $\Mix(H)$ is trivial for any (reflexive) dismantlable graph $H$.

In the case of the reconfiguration problem one finds a parallel between results for reflexive graphs and irreflexive graphs, and the topological techniques used are `cleaner' in the reflexive setting, so we start there.  The result from [1] that $\Mix(C)$ is $\coNP$-complete for any irreflexive odd cycle $C$ suggests, through this parallel, that $\Mix(C)$ should also be $\coNP$-complete for $C$ being any reflexive cycle of girth at least $4$.  Our goal was to prove this, but in doing so we found the proof could be extended, with not too much work to all triangle free reflexive graphs.

In [Lee et al., 2021], we adapted to results of Wrochna [Wrochna, 2015] for irreflexive graphs to reflexive graphs, and showed that $\Recon(H)$ is polynomial time solvable (for reflexive instances) for any triangle-free reflexive graph $H$.  As discussed above, this yields the following corollary.

For any triangle-free reflexive graph $H$, the problem $\Mix(H)$ is in the complexity class $\coNP$.

Clearly if $H$ is disconnected then $\Hom(G,H)$ is disconnected as soon as $G$ contains an edge, so we always assume that $H$ is connected.  $\Mix(H)$ can then be solved for an instance $G$ component-wise, so we will also assume that $G$ is connected.  If $H$ is a reflexive tree, then it is dismantlable,  in which case $\Mix(H)$ is trivial. In this paper, we prove completeness when $H$ has a non-trivial cycle, with the following theorem.

For any triangle-free reflexive non-tree $H$, the problem $\Mix(H)$ is $\coNP$-complete.

The proof depends on results from [Lee et al., 2021] and exploits the same connection to topology that is central to the algorithms there and in [Wrochna, 2015]. This lends support to the notion that topology may factor into the trichotomy classification.  We expect the proofs and results of this paper should yield somewhat messier irreflexive versions depending on [Wrochna, 2015] rather than on [Lee et al., 2021].

Finally, we note here, that our main technical theorem, Theorem <ref>, implies that $\Mix(H)$ is $\coNP$-Hard for a much larger class of reflexive graphs than triangle-free non-tree, but we do not have a corresponding proof that $\Recol(H)$ is in $\Poly$ unless $H$ is triangle-free, so we do not know that $\Mix(H)$ is in $\coNP$ for these graphs.

§ OUTLINE OF PROOF AND OF MAIN CONSTRUCTION

One of the essential features in many papers on recolouring and homomorphism reconfiguration is the simple fact that when mapping a cycle $B$ to another smaller cycle $C$ of girth at least $4$, (or $5$ if $B$ is not reflexive) the number of times that $B$ winds around $C$ is invariant under reconfiguration.   In [Wrochna, 2015], Wrochna, to great effect, extended this idea and showed that for a cycle $C$ mapped to graph $H$ the homotopy type of the image is invariant under reconfiguration.  We did the same for reflexive graphs in [Lee et al., 2021].
In this paper we use the slighly coarser, but computationally simpler topological invariant of homology.  We define homology properly in Section <ref>, but for the purposes of this outline, one unfamiliar with the concept benefits by thinking of $H$ as a cycle, and the `homology' of a cycle mapping to $H$ as being the number of times it winds around $H$; having trivial homology means it does not wind.

As $H$ is reflexive, there are always constant maps in $\Hom(G,H)$, and as $H$ is connected, it is easy to see that these are always in the same component of $\Hom(G,H)$. So to decide if $\Hom(G,H)$ is connected, one must decide if every $H$-colouring of $G$ reconfigures to a constant map.  In [Lee et al., 2021] we showed that an $H$-colouring of $G$ reconfigures to a constant map if and only if it has trivial homotopy (see Corollary <ref> below), and trivial homotopy is implied by trivial homology (see Lemma <ref>). So deciding if all $H$-colourings of $G$ have trivial homology is a subproblem of $\Mix(H)$.  Calling an $H$-colouring of $G$ flat if it has trivial homology, we reduce our task  to showing $NP$-completeness of the problem $\NF(H)$ of deciding if there is a non-flat $H$-colouring of an instance $G$ (see Lemma <ref>).

To prove this, we will reduce $3$-colouring to $\NF(H)$ via a gadget construction. Given an (irreflexive) instance $G$ of $3$-colouring, we construct an instance $G^*$ of $\NF(H)$ such that $G$ has a $3$-colouring if and only if $G^*$ has a non-flat homomorphism to $H$. Now, we give a overview of the construction.

The (categorical) product $A \times B$ of two graphs $A$ and $B$ is the graph with vertex set $V(A) \times V(B)$, in which $(a,b) \sim (a',b')$ if $a \sim a'$ in $A$ and $b \sim b'$ in $B$.
For a vertex $b$ of $B$, $A \times b$ is the subgraph induced on the vertices $\{ (a,b) \mid a \in A \}$. If $b$ has a loop, then this is an isomorphic copy of $A$. The subgraph $a \times B$ is defined similarly.

Where $P_\ell$ is the reflexive path on vertices ${0, \dots, \ell}$, it is well known, and easy to show, that the existence of a path $P_\ell$ from $\phi$ to $\psi$ in $\Hom(G,C)$ is equivalent to the existence of a homomorphism from $P_\ell \times G$ to $C$ that restricts on $0 \times G$ to $\phi$ and on $\ell \times G$ to $\psi$. For a cycle $C$, we refer to $P_\ell \times C$ as a path-of-cycles  and to each copy $i \times C$ of $C$ a slice of the path.

In Fact <ref>, we observe the basic fact that under a homomorphism of a path-of-cycles to $H$, all slices have the same homology.  This property of paths-of-cycles is the main building block in our construction of $G^*$.   Let $C$ be a smallest cycle in $H$.  $G^*$ will contain a special copy $Z$ of $C$, and for every vertex $v$ of $G$, three more copies $A_0^v, A_1^v$ and $A_2^v$ of $C$.

Using a gadget $S_3$ made of paths-of-cycles we will ensure that under a homomorphism $\phi:G^* \to H$, if $Z$ has non-trivial homology, then exactly one of the $A_i^v$ for each $v$ have the same homology as $Z$, and the other two have trivial homology.  For every edge $uv$ of $G$ we use another path-of-cycles gadget $S_2$ to ensure that not both  $A_i^v$ and $A_i^u$ get non-trivial homology. From this it will not be hard to show that if there is a non-flat homomorphism $\phi: G^* \to C$; one such that $Z$ has non-trivial homology, then we get a $3$-colouring of $G$ by mapping $v$ to the $i$ such that $A_i^v$ has non-trivial homology.

The construction as described above is not so difficult. The gadgets are constructed in Section <ref> and the rest of the construction is done in Section <ref>. However, we also have to show that if there is no $3$-colouring of $G$, then all homomorphism of $G^*$ to $H$ are flat.  It is not difficult to show that if there is no $3$-colouring of $G$, then any homomorphism of $G^*$ to $H$ has trivial homology on the slices of our path-of-cycles gadgets. This does not yet ensure that all $H$-colourings of $G^*$ are flat. There may be a lot of other `non-gadget' cycles in $G^*$ that also must have trivial homology.  This complicates the whole construction.

To deal with this we define a subgraph $T^*$ of $G^*$ that, in a way, contains all of these non-gadget cycles.  For each cycle in $T^*$, we will `plug' it by triangulating it to a new central vertex.  So that this does not break the necessary properties of $G^*$, we must build it, and the gadgets, so that we know the possible colourings on the vertices that will be in $T^*$.  So our gadget construction mentions a subgraph $T$ the copies of which will become part of $T^*$ in $G^*$.  The proof that the cycles in $T^*$ that we plug in this way are all the cycles that have to be plugged takes considerable work.  This proof is done in Section <ref> and the actual 'plugging' construction is then finished in Section <ref>.

§ THE HOMOLOGY OF A GRAPH

We recall the basic definitions of simplicial homology with coefficients in $\ZZ$. This is basically Section 2.1 of Hatcher [Hatcher, 2002] applied to the clique-complex of a graph $G$.

In the clique-complex $\DG$ of a graph $G$, an $n$-simplex is an ordered $(n+1)$-clique of $G$. As $G$ is reflexive, we consider multisets $[v,v,v]$, and $[u,v,u]$ when $u \sim v$, to be $3$-cliques.

The chain group $C_n(\DG)$ of $G$ is the (additive) group generated as a $\ZZ$-module over the set of $n$-simplices of $\DG$. Its elements are $n$-chains– sets of $n$-simplices.

Between these groups we have the boundary maps $\delta_n :C_n(\DG) \to C_{n-1}(\DG)$ defined on $n$-simplices by

\[ \delta_n([v_0,v_1, \dots, v_n]) = \sum_{i=1}^n (-1)^{i}[v_0,v_1, \dots, v_{i-1}, v_{i+1}, \dots, v_n], \]

and extended to the whole group additively.  (Note that $C_{-1}(\DG)$ is taken to be $0$, and $\delta_0$ the $0$-map.) For example, assume that $G$ has two $3$-cliques, $\{a,b,c\}$ and $\{a,d,b\}$.  The sum, $[a,b,c] + [a,d,b]$ say, is a $2$-chain.  Its boundary is

\begin{eqnarray*}
\delta( [a,b,c] + [a,d,b] )  & = &  [b,c] - [a,c] + [a,b]  + [d,b] - [a,b] + [a,d] \\
& = &  [a,d] + [d,b] + [b,c] - [a,c].\\
\end{eqnarray*}

Homology groups are defined using the boundary maps as follows.
The cokernel
$B_{i}(\DG):= \delta_{i+1}(C_{i+1}(\DG)) \leq C_i(\DG)$
of $\delta_{i+1}$ is the $i^{th}$ boundary group; its elements are $i$-boundaries.
The kernel $Z_i(\DG) = \ker(\delta_{i}) \leq C_{i}(\DG)$ is the
$i^{th}$ cycle group; its elements are $i$-cycles.
It is easy to check that $\delta_i \circ \delta_{i+1} = 0$ and so $B_i(\DG) \leq Z_i(\DG)$.
The $i^{th}$ homology group is $H_i(\DG) = Z_i(\DG)/B_i(\DG)$; its elements are classes of homologically equivalent cycles, though we often refer to these classes simply as cycles.

We start with some standard easy calculations.

For any connected graph $G$, $H_0(\DG) = \ZZ$.
Indeed, $C_0(\DG) = \angles{ [v] \mid v \in V(G) }$ and as $\delta_{-1}$ is the $0$ map,
$Z_0(\DG) = \ker{\delta_{-1}} = C_0(\DG)$.  On the other hand, $C_1(\DG) = \angles{ [u,v] \mid uv \in E(G) }$, so $B_0(\DG) = \delta_1(C_1) = \angles{ [u] - [v] \mid uv \in E(G) }$.
Thus $H_0(\DG) = Z_0(\DG)/B_0(\DG) = \ZZ$.

The following are all true for any triangle-free $G$.

* $C_2(\DG)$ is the free group generated by the set

\[ \{ [v,v,v] \mid v \in V(G)\} \cup \{ [u,u,v], [u,v,u], [v,u,u] \mid uv \in E(G)\} \]

* As $\delta([v,v,v]) = [v,v]$, and, for example, $\delta([u,v,u]) = [v,u] - [u,u] + [u,v]$,  one finds that $B_1(\DG) = \delta_2(C_2)$ is free generated by
\[ \{ [v,v] \mid v \in V(G) \} \cup \{ [u,v] + [v,u] \mid uv \in E(G) \}.  \]

It follows that $[v,u] = -[u,v]$ in $H_1(\DG)$ for every edge $uv$ of $G$.

* $Z_1(\DG)$ is free generated by cycles (including loops and $2$-cycles) in $G$.

* $H_1(\DG) = Z_1(\DG)/B_1(\DG)$ is free generated by the undirected edge-sets of cycles (not-including loops and $2$-cycles) in $G$.

* $H_n(\DG)$ is trivial; that is, has only the $0$ element; for $n \geq 2$.

In light of (3), we will often talk of a cycle $(x_0, x_1,  \dots, x_\ell, x_0)$ of $G$ as being in $Z_1(\DG)$. This really means the $1$-cycle

\[ [x_0,x_1] + [x_1,x_2] + \dots + [x_\ell, x_0]. \]

If $G$ is not triangle free, then a triangle such as $(u, v, w, u)$, which lives
in $Z_1(\DG)$ as $\sigma = [u,v] + [v,w] + [w,u]$ is a boundary in $B_1(\DG)$:

\[ \delta_2([u,v,w]) = [v,w] - [u,w] + [u,v] = [u,v] + [v,w] + [w,u], \]

so $[\sigma] = 0$ in $H_1(\DG)$.  Thus we still have that $H_1(\DG)$ is generated by undirected edges-sets of cycles in $G$, but it may no longer be free, and there can be more complicated boundaries as well. The groups $H_n$ for $n \geq 2$ are also not generally trivial, if $G$ is not triangle-free.

The group $Z_1(\DG)$ of $1$-cycles is what is often called the integral cycle space of $G$; as opposed to the cycle space, which we get with the same development using $\ZZ_2$ in place of $\ZZ$. (Often though $C_2(\DG)$ is taken to be empty, so $Z_1(\DG)$ is called $H_1(\DG)$.)
A cycle $C$ in $G$ is trivial if $[C] = 0$ in $H_1(\DG)$, where $0$ represents the class containing the empty cycle. If $H_1(\DG) = \{ 0 \}$ then we say $G$ has trivial homology. An $\NT$-basis of $G$ is a basis of $H_1(\DG)$; $\NT$ refers to the fact that it contains No Triangles. With triangles of $G$ it makes up a basis of the integral cycle space of $G$.

The following is the basic statement that all slices of a path of cycle get the same homology under any homomorphism.

Let $\phi: P_\ell \times C \to H$ be a homomorphism.  For all $j,k \in \{0,1, \dots, \ell\}$ we  have $[\phi(j \times C)] = [\phi(k \times C)]$ in $H_1(\DH)$.

Clearly it is enough to prove this for $j=0$ and $k=1$.
Observe that the boundary $\delta_2(c_i)$ of the $2$-chain

\[ c_i:= [(0,i), (0,i+1), (1,i) ] + [ (1,i), (0,i+1), (1,i+1)]\]

is the square

\[[(0,i), (0,i+1)] - [(0,i), (1,i)] - [(1,i),(1,i+1)] + [(0,i+1),(1,i+1)]. \]

So the boundary of the $2$-chain $\sum_{i = 0}^{\ell} c_i$ is
$(0 \times C) - (1 \times C)$, and so its image $\phi(0 \times C) - \phi(1 \times C)$
is also a boundary.
Thus $[\phi(0 \times C)] = [\phi(1 \times C)]$ in $H_1(\DH)$, as needed.

§ REDUCTION TO NON-FLAT $H$-COLOURING

In this section we reduce our main result to a problem called non-flat $H$-colouring.

A homomorphism $\phi: G \to H$ is flat if for all cycles $C$ in $G$, $[\phi(C)] = 0$ in $H_1(\DH)$. Equivalently $\phi$ is flat if $[\phi(C)] = 0$ for all cycles $C$ in an $\NT$-basis of $G$.

Consider the following problem.

A graph $G$.
Is there a non-flat homomorphism of $G$ to $H$?

We will prove the following.

Let $H$ be a reflexive graph such that $H_1(\DH)$ is free and non-trivial.
The problem $\NF(H)$ is $\NP$-hard.

The proof of this takes up most of the paper, but for the rest of this section, we show that it implies Theorem <ref>. We need a result from [Lee et al., 2021] where homotopy classes of cycles in a graph are defined.

Let $\Pi(H;x_0)$ be the graph whose vertices are cycles in $H$ starting at $x_0$, and in which a cycle $Y$ is adjacent to a cycle $X = (x_0, \dots, x_\ell,x_0)$ if either of the following are true:

$Y = (x_0,x_1, \dots, x_{i-1},x_i,x_i,x_{i+1},\dots, x_\ell,x_0)$ for any $i$, or

$Y = (x_0,x_1, \dots, x_{i-1},x'_i,x_{i+1}, \dots, x_\ell,x_0)$ for some $i \notin \{0,\ell\}$, where $x_{i-1}=x_{i+1}$.

Let $\Pi(H)$ be the graph we get from the disjoint union, over all $x_0 \in V(H)$, of $\Pi(H;x_0)$
by adding an edge between walks $y$ and $x = (x_0,x_1, \dots,x_{\ell-1},x_0)$ if

P3(P3) $y = (x_1, \dots, x_{\ell-1})$ and $x_1 = x_{\ell-1}.$

Observe that if $H$ is connected, then all the constant cycles, those in which all vertices are the same, are in the same component of $\Pi(H)$. A cycle is contractible if it is in the same component of $\Pi(H)$ as the constant cycles.

The following is from [Lee et al., 2021].

A homomorphism $\phi$ in $\bHom(G,H)$ is in the constant component of $\bHom(G,H)$ if
for every cycle $C$ in $G$, $\phi(C)$ is contractible in $\Pi(H)$.

Now observe the following analog of a well known idea of topology.

Let $H$ be a triangle-free reflexive graph.
If $[\phi(C)]$ is trivial in $H_1(\DH)$, then $\phi(C)$ is contractible in $\Pi(H)$.

Our proof is by induction on the length of $\phi(C)$, it is clearly true of cycles of length $1$.
Let $\phi(C) = (x_0, \dots, x_\ell,x_0)$, for $\ell \geq 1$.
As a cycle in $Z_1(\DH)$ we write this as

\[ [x_0,x_1] + [x_1,x_2] + \dots + [x_\ell,x_0]. \]

If the negation of some element in the chain appears later in the chain: $[x_j, x_{j+1}] = [x_{i+1}, x_i]$ for some $i < j$, then these disappear in $H_1(\DH)$, and we get in $H_1(\DH)$ that
$[ \phi(C) ] = [C_1] + [C_2]$ where

\[ C_1 = [x_{i+1}, x_{i+2}] +  \dots + [x_{j-1}, x_j] \mbox{ and } C_2 = [x_{j+1}, x_{j+1}] + \dots +[x_{i-1}, x_i] \]

with indices modulo $\ell$ (one of these might be empty).  The result therefore follows by induction.

So we may assume that the $1$-chain $\phi(C) =  [x_0,x_1] + [x_1,x_2] + \dots + [x_\ell,x_0]$ consists of non-negated summands.   But as $Z_1(\DH)$ is free and $B_1(\DH)$ is as given in Example <ref>(2) the fact that $\phi(C) = 0$ means that all summands in this chain are $[x_0,x_0]$, and so $\phi(C)$
is constant, and so contracible in $\Pi(H)$.

Thus from Corollary <ref> we get the following.

Let $H$ be a triangle-free reflexive graph. If $\phi: G \to H$ is flat in $H_1(\DH)$, then $\phi$ is in the constant component of $\bHom(G,H)$.  If all homomorphisms $\phi: G \to H$ are flat, then $\bHom(G,H)$ is connected.

With this we can show the following.

If $\NF(H)$ is $\NP$-complete for a triangle-free reflexive cycle $H$, then $\Mix(H)$ is $\coNP$-complete.

We observe that the negation of $\NF(H)$ can be solved by $\Mix(H)$.  Indeed let $G$ be an instance of $\NF(H)$.  If it is a YES instance, then there is a non-flat homomorphism $\phi: G \to H$.  Thus for some cycle $B$ of $G$, $[\phi(B)] \neq 0$. By Lemma <ref> we have then that $\phi$ is non-contracible in $\Pi(H)$, so $G$ is NO instance of $\Mix(H)$.

On the other hand, if $G$ is a NO instance of $\NF(H)$ then all homomorphisms $\phi: G \to H$ are flat, and so by Lemma <ref> and Corollary <ref> reconfigure to constant homomorphisms.  Thus $G$ is a YES instance of $\Mix(H)$.

Observe now that Theorem <ref> follows from Theorem <ref>.

Let $H$ be a triangle-free reflexive graph containing a cycle.  By Example  <ref>(4) $H_1(\DH)$ is free, and as it contains a cycle, it is non-trivial,
so we may apply Theorem <ref> to get that $\NF(H)$ is $\NP$-complete.  Lemma <ref> then tells us that $\Mix(H)$ is $\coNP$-complete. So Theorem <ref> is proved.

For the rest of the paper, we therefore concentrate on proving Theorem <ref>.

§ THE HOMOLOGY SUM GADGET

Let $\sH$ be a connected triangle-free reflexive graph with non-trivial homology, and let $\sC = (0,1, \dots, g-1, 0)$, for $g \geq 4$ be a particular shortest non-trivial cycle in $\sH$.  Throughout most of the rest of the paper, $\sH$ and $\sC$ will always be assumed to have these properties.

[scale=.7, every node/.style = vert]
ı[evaluate=ıas using 90 - (30*ı),
evaluate=ıas using int(Mod(-ı,12))] in 0,...,11

(:3cm) + (-5,0) node (2ı) ;
(:4cm) + (-5,0) node (3ı) ;

(:3cm) + (5,0) node (6) ;
(:4cm) + (5,0) node (5) ;
ı[evaluate=ıas using (ı-3)/4] in 0,1,2,3,4,5,6
($(3\i)!0.33!(5\i)$) + (0,) node (1aı) ;
($(3\i)!0.67!(5\i)$) + (0,) node (2aı) ;
(3ı) – (1aı) – (2aı) – (5ı);

ı[evaluate=ıas using int(Mod(ı+1,12))] in 0,...,11

ı[evaluate=ıas using int(ı+1)] in 0,...,5

[pattern=north west lines, pattern color=gray] (-5,0) circle (3cm);
[pattern=north west lines, pattern color=gray] (5,0) circle (3cm);

[xshift = -5cm]
[draw, red, use Hobby shortcut, fill=red!50, opacity=.5]
(-.2,3) arc (180:0:.2) arc (180:240:5) arc (60:-120:.2) arc (60:120:5) arc(300:120:.2) arc (-60:0:5) – cycle;

[xshift = 5cm]
[draw, red, use Hobby shortcut, fill=red!50, opacity=.5]
(0,2.8) arc (270:90:.2) arc (90:30:3.2) arc (30:-150:.2) arc (30:90:2.8) – cycle;
[draw, red, use Hobby shortcut, fill=red!50, opacity=.5]
(2.8,0) arc (180:0:.2) arc (0:-60:3.2) arc (300:120:.2) arc (-60:0:2.8) – cycle;
[draw, red, use Hobby shortcut, fill=red!50, opacity=.5]
(0,-2.8) arc (90:-90:.2) arc (270:210:3.2) arc (210:30:.2) arc (210:270:2.8) – cycle;
[draw, red, use Hobby shortcut, fill=red!50, opacity=.5]
(-2.8,0) arc (360:180:.2) arc (180:120:3.2) arc (120:-60:.2) arc (120:180:2.8) – cycle;

Sum gadget $S_s$ for $g=4$ and $s=3$ from Construction <ref>.
The graph show (with some vertices in the back not visible) is the path $P_5 \times \sB$ of six $12$-cycles.  The inner circle on the right is the slice $\ell \times \sB$; identifying the four sets of vertices highlighted gives $S_3^{(1)}$ in step (1) of the construction.
The inner cycle on the left is the slice $0 \times \sB$; identifying the three highlighted vertices of this cycle makes $S_3^{(2)}$ in step (2) of the construction.   This creates three $4$-cycles, and in step (3) we would add a new cycle adjacent to each of them to make $S_s$.

[scale=.65, every node/.style = vert]

ı[evaluate=ıas using 90 - (30*ı),
evaluate=ıas using int(Mod(-ı,12))] in 0,...,11
(:2cm) + (-5.5,0) node (1ı) ;
(:3cm) + (-5,0) node (2ı) ;
(:2cm) + (5.5,0) node (7) ;
(:3cm) + (5,0) node (6) ;

ı[evaluate=ıas using int(Mod(ı+1,12))] in 0,...,11

ȷ[evaluate=ȷas using 5 - 3*cos(90 - (30*ȷ)),
evaluate=ȷas using 3*sin(90 - (30*ȷ)) - ] in 0,...,5,11

ı[evaluate=ıas using 90 + (4-ı)*(90/4)] in 3,...,5
(1.41**cos(),1.41**sin()) node (ıȷ) ;

[evaluate=as ıusing int(Mod(-1,12))] in 0,...,5
ȷ[evaluate=ȷas using int(ȷ+ 1)] in 2,3,4,5             ȷı

[pattern=north west lines, pattern color=gray] (-5.5,0) circle (2cm);
[pattern=north west lines, pattern color=gray] (5.5,0) circle (2cm);

[xshift = -5.5cm]
[draw, red, use Hobby shortcut, fill=red!50, opacity=.5]
(-.2,2) arc (180:0:.2) arc (180:240:3.3) arc (60:-120:.2) arc (60:120:3.3) arc(300:120:.2) arc (-60:0:3.3) – cycle;

[xshift = 5.5cm]
[draw, red, use Hobby shortcut, fill=red!50, opacity=.5]
(0,2.8) arc (270:90:.2) arc (90:30:2.2) arc (30:-150:.2) arc (30:90:2.8) – cycle;
[draw, red, use Hobby shortcut, fill=red!50, opacity=.5]
(2.8,0) arc (180:0:.2) arc (0:-60:2.2) arc (300:120:.2) arc (-60:0:2.8) – cycle;
[draw, red, use Hobby shortcut, fill=red!50, opacity=.5]
(0,-2.8) arc (90:-90:.2) arc (270:210:2.2) arc (210:30:.2) arc (210:270:2.8) – cycle;
[draw, red, use Hobby shortcut, fill=red!50, opacity=.5]
(-2.8,0) arc (360:180:.2) arc (180:120:2.2) arc (120:-60:.2) arc (120:180:2.8) – cycle;

[xshift = 10cm, rotate=-90]
ı[evaluate=ıas using 90 - (30*ı),
evaluate=ıas using int(Mod(-ı,12))] in 0,...,11
(:3cm) + (-5,0) node (2ı) ;
(:3cm) + (5,0) node (6) ;

ı[evaluate=ıas using 90 - (90*int(floor(Mod(-ı,12)/3))))] in 0,...,11
(:2cm) + (5.5,0) node[fill=red] (7ı) ;

(0,0) + (-5,0) node[fill=red] (10) ;
(1.5*cos(60),1.5*sin(60)) + (-5,0) node (11) ;
(2*cos(30),2*sin(30)) + (-5,0) node (12) ;
(1.5*cos(0),1.5*sin(0)) + (-5,0) node (13) ;
(0,0) + (-5,0) node[fill=red] (14) ;
(1.5*cos(-60),1.5*sin(-60)) + (-5,0) node (15) ;
(2*cos(-90),2*sin(-90)) + (-5,0) node (16) ;
(1.5*cos(-120),1.5*sin(-120)) + (-5,0) node (17) ;
(0,0) + (-5,0) node[fill=red] (18) ;
(1.5*cos(180),1.5*sin(180)) + (-5,0) node (19) ;
(2*cos(150),2*sin(150)) + (-5,0) node (110) ;
(1.5*cos(120),1.5*sin(120)) + (-5,0) node (111) ;

(.5*cos(30),.5*sin(30)) + (-5,0) node (00) ;
(1.2*cos(60-10),1.2*sin(60-10)) + (-5,0) node (01) ;
(1.5*cos(30),1.5*sin(30)) + (-5,0) node (02) ;
(1.2*cos(0+10),1.2*sin(0+10)) + (-5,0) node (03) ;
(.5*cos(-90),.5*sin(-90)) + (-5,0) node (04) ;
(1.2*cos(-60-10),1.2*sin(-60-10)) + (-5,0) node (05) ;
(1.5*cos(-90),1.5*sin(-90)) + (-5,0) node (06) ;
(1.2*cos(-120+10),1.2*sin(-120+10)) + (-5,0) node (07) ;
(.5*cos(150),.5*sin(150)) + (-5,0) node (08) ;
(1.2*cos(180-10),1.2*sin(180-10)) + (-5,0) node (09) ;
(1.5*cos(150),1.5*sin(150)) + (-5,0) node (010) ;
(1.2*cos(120+10),1.2*sin(120+10)) + (-5,0) node (011) ;

ı[evaluate=ıas using int(Mod(ı+1,12))] in 0,...,11

/i̱n 0/1, 1/2, 2/3, 3/0, 4/5, 5/6, 6/7, 7/4, 8/9, 9/10, 10/11, 11/8

ȷ[evaluate=ȷas using 5 - 3*cos(90 - (30*ȷ)),
evaluate=ȷas using 3*sin(90 - (30*ȷ)) - ] in 0,...,5,11

ı[evaluate=ıas using 90 + (4-ı)*(90/4)] in 3,...,5
(1.41**cos(),1.41**sin()) node (ıȷ) ;

[evaluate=as ıusing int(Mod(-1,12))] in 0,...,5
ȷ[evaluate=ȷas using int(ȷ+ 1)] in 2,3,4,5             ȷı

[pattern=north west lines, pattern color=gray] (-5.5,0) circle (2cm);
[pattern=north west lines, pattern color=gray] (5.5,0) circle (2cm);

Sum gadget $S_s$ for $g=4$ and $s=3$: On the left is the path-of-cycles $S_s^{(1)}$ with $7$ slices, a stylized quadrangulation of a cylinder, with vertices that will be identified in $S_s^{(2)}$ indicated. On the right the indentifications have been made, making $S_s^{(2)}$. This is completed to $S_s = S_s^{(3)}$ in a lighter colour.

For an integer $n$ let $[n]$ denote the set $\{0,1, \dots, n-1\}$.
Let $\sB$ be the symmetric reflexive cycle of girth $s \cdot g$. Writing its vertex set as $V(\sB) = \{ ig + j \mid i \in [s], j \in [g] \}$, define the following maps, which are clearly in $\Hom(\sB,\sC)$. Define  $\beta: \sB \to \sC$ by
\[ \beta(ig + j ) = i, \]
and for $k \in [s]$ define $\alpha_k: \sB \to \sC$ by
\[ \alpha_k(ig + j ) = \PWF{j}{k = i}{0}{\mbox{ otherwise.}} \]
Thus $\beta$ maps the first $s$ vertices of $\sB$ to $0$, the next $s$ vertices to $1$, etc.,  while $\alpha_k$ maps all vertices to $0$ except the $k^{th}$ run of $g$ vertices which it maps  around $\sC$. Observe that there are paths from $[\beta]$ to $[\alpha_0]$, and from $[\alpha_0]$ to $[\alpha_1]$ to $\dots$ to $[\alpha_k]$ in $\bHom(\sB ,\sC)$ in which the first vertex is always $0$.
In the case of $(s,g) = (3,4)$ for example, writing $f: \sB \to \sC$ as $f(0)f(1), \dots, f(s\cdot g)$ it is easy to find such a path

\[000111222333 \sim 011111222333 \sim 012222222333 \sim 012333333333 \sim 012300000000 \]

from $\beta$ to $\alpha_0$ and

\[012300000000 \sim 001230000000 \sim 000123000000 \sim \dots \sim 000001230000 \]

from $\alpha_0$ to $\alpha_1$.

From this it is not too hard to see that the following is true.

There is an integer $\ell = \ell_s \geq 2$ such that for each $i \in [s]$ there
is a homomorphism $\phi_i : P_\ell \vtimes \sB \to \sC$ such that

* $\phi_i|_{0 \times \sB} = \alpha_i$, and

* $\phi_i|_{\ell \times \sB} = \beta$, and

* $\phi_i$ is constant $0$ on $T:= P_\ell \times 0$.

With this $\ell$ we are now ready to construct $S_s$, as shown in Figure <ref>.

Let $S_s$ be constructed from $\ccP = P_\ell \vtimes \sB$, where $\ell = \ell_s$,

as follows.

* In the last slice $\ell \times \sB$ of $\ccP$, for each $j \in [g]$ identify the vertices in the set

\[ \{ (\ell, i + js) \mid i \in [s]. \} \]

This results in a copy of $\sC$ that we refer to as $\sC$ (in $S_s$).

* In the first slice $0 \times \sB$ of $\ccP$, identify the vertices in the set

\[ \{ (0, ig) \mid i \in [s]. \} \]

This creates $s$ copies of $\sC$ sharing the vertex $(0,0)$. Refer to these as $A_0', \dots, A_{s-1}'$.

* For each $i \in [s]$, take a new copy of $P_1 \times \sC$; identify one slice of it with $A_i'$ and call the other slice $A_i$.

Let $S_s^{(i)}$ be the graph constructed in step (i) of the construction. Observe that the identifications in steps (1) and (2), can be viewed as homomorphisms $q_1: \ccP \to S_s^{(1)}$ and $q_2: S_s^{(1)} \to S_s^{(2)}$. Notationally we should use names such as $q_2 \circ q_1( (\ell, 0) )$ for vertices of $ S_s^{(2)} \leq S_s^{(3)}$ but the abuse of calling this $(\ell, 0)$ is convenient and does not cause problems.

This allows us the following definition that we will need later.

A cycle in $S_s$ is a gadget-cycle if it is
a slice $i \times \sB$ of $\ccP$ or is $A_i$ for some $i$.  The cycles $A_i$ and $Z$ are end gadget-cycles.

Before we prove the necessary properties of this construction, we recall some standard algerbraic notions about homomorphisms.

Given an equivalence relation $\Theta$ of $V(G)$, the  quotient graph $G_{/\Theta}$ is the  graph with vertex set $\Theta$ such that $\ec{u} \sim \ec{v}$ if there are $u' \in \ec{u}$ and $v' \in \ec{v}$ with $u' \sim v'$.
The kernel of a homomorphism $\phi: G \to H$ is the
equivalence relation

\[ \{ \phi^{-1}(h) \mid h \in V(H) \} \]
of  $V(G)$.
The following facts are well known and easy to show.

Let $G$ and $H$ be graphs. DO WE NEED PART (1) ?

* For any refinement $\Theta$ of $\ker(\phi)$  the quotient map

\[ \phi_{/\Theta} : G_{/\Theta} \to H: \ec{u} \mapsto \phi(u) \]

is a well defined homomorphism.

* For any equivalence $\Theta$ of $G$ and homomorphism $\phi: G_{/\Theta} \to H$,
the lift

\[ \phi^\Theta: G \to H: g \mapsto \phi(\ec{u}) \]

is a well defined homomorphism.

With this observation we prove the following desired properties of $S_s$.

The graph $S = S_s$ contains end gadget-cycle copies $Z,A_0, \dots, A_{s-2}$ and $A_{s-1}$ of $\sC$, which are pairwise distance at least $2$ apart;  and a tree $T = T(S)$ that
contains the copy of $0$ in each of these end gadget-cycles.
Further, for any $\sH$ whose smallest homologically non-trivial cycle is $\sC$ the following are true.

* For any homomorphism $\Gamma: S \to H_*$, if $[\Gamma(Z)] = 0$, then $[\Gamma(C)]=0$ for all gadget cycles $C$ of $S$ except possibly the $A_i$.

* For any homomorphism $\Gamma :S \to \sH$, we have

\[ [ \Gamma(Z) ] = \sum_{i \in [s]} [\Gamma(A_i)]. \]

* For each $i \in [s]$ there is a homomorphism $\Gamma_i: S \to \sH$
such that $[\Gamma_i(A_i)] = [\sC]$ and such that $\Gamma_i$ is $0$ on
$T$ and $A_j$ for $j \neq i$.

The statements before the 'Further' are just recollections of the construction.

For part (1), let $\Gamma: S \to \sH$ be a homomorphism with $[\Gamma(\sC)] = 0$. So $\Gamma' = \Gamma \circ (q_2 \circ q_1)$ has $[\Gamma'(0 \times \sC)] = 0$. By Fact <ref> we thus get $[\Gamma'(i \times \sC)] = 0$ for all $i \in [\ell]$, and thus $[\Gamma(i \times \sC)] = [\Gamma(q_2 \circ q_1(i \times \sC))] = 0$, as needed.

For part (2), let $\Gamma$ be any homomorphsim of $S$ to $\sH$.

Where $\ccP$ is as in Construction <ref>,
$(q_2 \circ q_1)(\ell \times \sC) = Z$ and $(q_2 \circ q_1)(0 \times \sC) = \sum_{i \in [s]}A'_i$, so
the homomorphism $\Gamma' = \Gamma \circ (q_2 \circ q_1): \ccP \to S_s^{(2)} \to \sC$ satisfies

\[  [\Gamma'( \ell \times \sC )] = [\Gamma(Z)]  \mbox{ and } [\Gamma'(0 \times \sC)] = \sum [\Gamma(A'_i)]. \]

As the left sides of these equalities are equal by Fact <ref>, so are the right
sides. Using Fact <ref> again on the path of cycles connecting $A_i$ and $A_i'$ we get (2).

Now let $T$ be the tree in $S_s$ induced by the vertices $(i, 0)$ in $S^{(2)}_s$ and the vertex $0$ in $A_i$ for each $i$.
To get part (3), let $\Gamma'_i = (q_2 \circ q_1) \circ \phi_i$ where $\phi_i$ is from Fact <ref>, and extend $\Gamma'_i$ to $\Gamma_i: S_s \to C$ by letting it act on $A_i$ as is does on $A'_i$.

§ THE PRELIMINARY CONSTRUCTION

Having built our gadget $S_s$, our main construction, that of $\Gb$, will be completed in two stages. In this section, we do the first stage, constructing, for every (irreflexive) instance $G$ of $3$-colouring, a graph $\Ga$ containing a designated copy $\sZ$ of $\sC$, which satisfies
the properties listed in Lemma <ref>.  This construction was outlined in Section <ref>.

For an irreflexive graph $G$ construct $\Ga$ as follows.

* For every vertex $v$ of $G$ let $\Ga$ contain three copies $A^v_0, A^v_1$ and
$A^v_2$ of $\sC$. Let $\Ga$ also contain a copy $\sZ$ of $\sC$. Let all of these be

* For every vertex $v$ of $G$ create a new copy $S^v$ of the sum gadget $S_3$;
identify the copy of $Z$ in $S^v$ with $\sZ$, and for each $i \in [3]$ identify the copy of $A_i$ in $S^v$ with $A^v_i$ .

* For every vertex $v$ of $G$ and every pair of distinct indices $i < j \in [3]$,
create a new copy $S^v_{i,j}$ of $S_2$; identify its copy of $A_0$ with $A^v_i$ and its
copy of $A_1$ with $A^v_j$. However, in identifying this copy of $A_1$ with $A^v_j$
identify the copy of the vertex $i$ in $A_1$ with the vertex $g-i$ in $A^v_j$.

* For each edge $uv$ in $G$ and each $i \in [3]$, create a new copy $S_i^{uv}$ of $S_2$;     identify its copy of $A_0$ with $A_i^u$ and its copy of $A_1$ with $A_i^v$.

Let $\Ga[i]$ refer to the graph constructed in step (i) of the construction.

For each sum gadget $S$ used in the construction, Lemma <ref> gives us a subgraph $T(S)$ containing the vertex $0$ of every gadget-cycle.  Let $\sT \leq \Ga$ be the union of all these $T(S)$.

First we observe some easy properties of the construction, then prove the main properties.

A cycle of $\Ga$ is a gadget-cycle if it is a gadget-cycle in one of the gadgets $S_s$ used in constructing $\Ga$.

Where $\Ga$ is constructed from a graph $G$ by Construction <ref>, the following are true.

* The subgraph $\sT \leq \Ga$ is connected.

* The order $|V(\Ga)|$ is polynomial in $|V(G)|$.

To see (1) observe that $\Ga$ is the union of copies of $S_3$ and $S_2$ that are attached by identifying end gadget-cycles.  The vertices $0$ in these, which are in $\sT$, are always identified.

For (2) we observe that $\Ga$ consists of $|V(G)| = O(n)$ copies of $S_3$ and  $3(|V(G)| + |E(G)|) = O(n^2)$ copies of $S_2$; these have constant order.

We now prove the main properties of the construction. Recall that $\sH$ is a graph with non-trivial homotopy and $\sC$ is a
non-trivial cycle of $\sH$ of minimum girth.

There is a homomorphsim $\phi: G \to K_3$ if and only if there is a homomorphism
$\phi^*: \Ga \to \sH$ such that $[\phi^*(\sZ)] = [C]$ for some copy $C$ of $\sC$ in $\sH$. Moreover, if there is such a homomorphism $\phi^*: \Ga \to \sH$, we may assume that it is constant $0$ on the subgraph $\sT$ of $\Ga$.

Before we prove Lemma <ref>, we prove one fact, that we will use again later.
This was the point of step (2) of Construction <ref>.

For any homomorphism $\phi^*:\Ga \to \sH$ and any $v \in V(G)$, either

* $[\phi^*(Z)] = 0$ and $[\phi^*(A_i^v)] = 0$ for all $i \in [3]$, or

* $[\phi^*(Z)] \neq 0$ and exactly one of the $[\phi^*(A_i^v)]$ are equal to this, the other two are $0$.

By Example <ref>(3), $H_1(\DsH)$ is a free group. As $Z$ and $A_i^v$ have the girth of the minimal cycle of $\sH$, their images under $\phi^*$ are either $0$ or generators of $H_1(\DsH)$. The paths-of-cycles introduced in step (2) of Construction <ref> preclude the possibility that two of the $[\phi^*(A_i^v)]$ have opposite signs, so item (2) of Lemma <ref> yields the claim.

We are now ready to  prove Lemma <ref>.

One the one hand, assume that there is a homomorphism $\phi^*:\Ga \to \sH$ with
$0 \neq [\phi^*(\sZ)] =: [C]$.
To define $\phi: G \to K_3$, consider some $v \in V(G)$.
As $\sZ$ is identified with the copy of $Z$ in  $S^v \cong S_3$,
we have by (2) of Lemma <ref> and Claim <ref>,
that $[A_i^v] = [C]$ for exactly one $i \in [3]$.
Let $\phi(v)$ be this $i$. This defines a mapping $\phi: V(G) \to V(K_3)$.
Now, for any edge $uv$ of $G$ we have $\phi(u) \neq \phi(v)$,
as if $\phi(u) = i = \phi(v)$ then  $\phi^*$ restricted to
$S_i^{uv} \cong S_2$ has
$[\phi^*(A_0)] = [\phi^*(A_1)] = [\sC]$, which violates (2) of Lemma <ref>.   Thus $\phi: G \to K_3$ is a homomorphism.

Assume, on the other hand, that there is a homomorphism $\phi: G \to K_3$.
We define  $\phi^*: \Ga[2] \to \sH$ by choosing a particular copy $C$ of $\sC$ in $\sH$ and defining
$\phi^*: \Ga[2] \to C$ as follows. For each $v$ let
$\phi^*$ restricted to $S^v$ be $\Gamma_{\phi(v)}$ from Lemma <ref>.
These all agree on the copies of $Z$, so this is well defined, and has
$[\phi^*(\sZ)] = [C]$ as needed.
Further, if $\phi(v) = i$ then $\phi^*$ is constant $0$ on
$A_j^v$ for $j \neq i$ and maps $A_i^v \cong \sC$ identically to $C$.

Now we extend $\phi^*$ to a homomorphism $\Ga[3] \to C$.
For each vertex $u$ of $G$, let the copy $S^u_{i,j}$, for $i < j$,
be coloured with the colouring $\Gamma_0$ if $\phi(v) = i$, with colouring
$\Gamma_1$ if $\phi(v) = j$, and with the constant $0$ colouring otherwise.
This agrees with $\phi^*$ defined on $\Ga[2]$ on the cycles $A_i^v$, so is
well defined.

Finally, we extend $\phi^*$ to a homomorphism $\Ga \to C$.
For each edge $uv$ of $G$ and $i \in [3]$, at most one of $\phi(u)$ and $\phi(v)$
is $i$.
Let $\phi^*$ be $\Gamma_0$ (from Lemma <ref>) on $S_i^{uv}$ if
$\phi(u) = i$,  be $\Gamma_1$ if $\phi(v) = i$, or
be constant $0$ if neither of these holds.
This agrees with the definition of  $\phi^*$ on $\Ga[2]$, so is well defined.

This lemma tells us that there is a $3$-colouring of $G$, then there is a non-flat $H$-colouring of $\Ga$. On the other hand, we have seen that
if there are no $3$-colourings of $G$,  then all $H$-colourings of $\Ga$ are trivial on $\sZ$. However we have to show that they are trivial on all cycles.
Before we move onto the second stage of the construction, which will allow us to prove this, we observe that we are already partially there. We see that all $H$-colourings of $\Ga$ are trivial on all gadget-cycles.

For a homomorphism $\phi\colon \Ga \to \sH$ such that $[\phi(\sZ)] = 0$, we have that $[\phi(C)] = 0$ for every gadget-cycle $C$ of $\Ga$.

Assume that $\phi\colon \Ga \to \sH$ satisfies $[\phi(\sZ)] = 0$.  The lemma follows by item (1) of Lemma <ref> and by Claim <ref>.

Observing that the maps $\phi^*$ in the proof of Lemma <ref> are in fact
retractions to $\sZ$ we get from this, and the fact that $K_3$-colouring is $NP$-complete,
the following well known fact.

The problem $\Ret(C)$ for the reflexive cycle $C$ of girth $g \geq 4$,
is NP-complete.

§ COMPUTING THE $\NT$-BASIS

Recall that $\sT$ is the subgraph of $\Ga$ consisting of the special subgraph $T(S)$ of each of the sum gadgets $S$ used in its construction.   In this section, we prove the following.

$\Ga$ has a $\NT$-basis consisting only of
gadget-cycles and the cycles in an $NT$-basis of $\sT$.

The graph $\Ga$ is constructed from many copies of the path-of-cycles
by taking quotients (which includes contracting edges), and gluing things together. Homology provides us the tools of excision and Mayer-Vietoris sequences to compute homology groups under these operations.  Working through the steps of Constructions <ref> and <ref> with these computational tools we will find $\NT$-bases of $S_s$ and then $\Ga$. First though, as a path-of-cycles is a product, we compute its homology via a Künneth formula.

§.§ The $\NT$-basis of a path-of-cycles

We first compute an $\NT$-basis of a path-of-cycles $P_{\ell} \times C$.
The notation $\bbP_\ell \times \DsC$ is ambiguous as the product space of the clique complexes $\bbP_\ell$ and $\DsC$ is not the same as clique-complex of the product $P_\ell \times \sC$. Indeed the product $P_\ell \times C$ is shown on the left of Figure <ref> as a tiling of a cylinder with copies of $K_4$, while the product space $\bbP_\ell \times \DsC$ (see [Hatcher, 2002] pp.277-278), shown on the right, is a triangulation of a cylinder.

[scale=.7, every node/.style = vert]

ı[evaluate=ıas using 90 - (30*ı),
evaluate=ıas using int(Mod(-ı,12))] in 0,...,11
(:2cm) + (-5,0) node (1ı) ;
(:3cm) + (-5,0) node (2ı) ;
(:4cm) + (-5,0) node (3ı) ;
(:2cm) + (5,0) node (7) ;
(:3cm) + (5,0) node (6) ;
(:4cm) + (5,0) node (5) ;

ı[evaluate=ıas using int(Mod(ı+1,12))] in 0,...,11

Products of a path and a cycle: on the left is the graph product, on the right is the product as simplicial complexes

It is not too hard to see that the triangulation embeds in the $K_4$-tiling, and that, as simplicial complexes, the $K_4$-tiling deformation retracts to the triangulation.
So the two simplicial complexes have isomorphic homology groups.
For the following calculation, therefore, which says that any one gadget-cycle in a path-of-cycles can be taken as an $\NT$-basis for the path-of-cycles, we may assume that these two products coincide.

For any integer $\ell \geq 1$ and $d \geq 4$, and any $i \in [\ell]$,

\[ H_1(\bbP_\ell \times \DsC) = \angles{i \times C} \cong \ZZ. \]

The  Künneth formula (see Theorem 3B.7 of [Hatcher, 2002]
gives us that

\[H_k(\bbP_\ell \times \DsC) = \bigoplus_{i+j=k} H_i(\bbP_\ell) \otimes_{\ZZ} H_j(\DsC) \]

where $\oplus$ is the direct product of groups and $\otimes_{\ZZ}$ is the tensor product over $\ZZ$.
Thus we get

\begin{eqnarray*}
H_1(\bbP_\ell \times \DsC) & = & (H_1(\bbP_\ell) \otimes_{\ZZ} H_0(\DsC))
\oplus   (H_0(\bbP_\ell) \otimes_{\ZZ} H_1(\DsC)) \\
& = &  (0 \otimes_\ZZ \ZZ) \oplus (\ZZ \otimes_\ZZ \ZZ) \\
& = &  0 \oplus \ZZ = \ZZ,
\end{eqnarray*}

as needed. That the generator can be taken as any slice $i \times C$ seems clear.

§.§ Excision and Mayer-Vietoris Sequences

Our main tools are excision for dealing with quotients, and Mayer-Vietoris sequences for patching together gadgets.
For these we will use the reduced homology groups $\tilde{H}_i(\DG)$, which are defined on page 110 of [Hatcher, 2002]. When $i \geq 1$ we have  $\tilde{H}_i(\DG) = H_i(\DG)$, but for $i = 0$ we have  $\tilde{H}_0(\DG) \oplus \ZZ \cong H_0(\DG)$. So whereas the dimension of $H_0(\DG)$ is the number of components of $G$, the dimension of $\tilde{H}_0(\DG)$ is one less than the number of components. Generally we use connected $G$ so $\tilde{H}_0(\DG)$ is usually $0$.

Recall also that a sequence of groups

\[
\dots \to M_{i+2} \goes{\alpha_{i+2}}    M_{i+1} \goes{\alpha_{i+1}}  M_i \goes{\alpha_i} M_{i-1} \to \dots
\]

is exact if for each $i$, $\alpha_{i} \circ \alpha_{i+1} = 0$, and that if a we have a short exact sequence of groups

\[ 0 \to A \to B \to C \to 0, \]

where $C$ is free, then the sequence splits (see [Hatcher, 2002] p. 148), which means that $B = A \oplus C$.

The following is a special case of the process known as excision. It tells us that when contracting an edge not in a $C_4$, our $\NT$-basis is unchanged.

Let $uv$ be an edge of $G$ that is in no induced copy of $C_4$, and let
$G' = G / uv$ be the graph  we get by contracting the edge $uv$.
Then $ [C]\mapsto [C / uv]$ is an isomorphism $H_1(\DG) \cong H_1(\DG')$.

As $uv$ is in no $C_4$, contracting it makes no new $K_3$, so no new $2$-simplices.
Thus, as simplicial complexes, $\DG'$ is exactly the quotient $\DG/\DE$
where $\DE$ is the simplicial complex of the edge $uv$.

Take an epsilon neighbourhood in $\DG$ around $\DE$.
It consists of $\DE$ and little nubs of edges and some frills of triangles. These
all deformation retract to $\DE$ so we can apply excision
(Thm 2.13 of [Hatcher, 2002]) to
get that

\[  H_1(\DE) \to H_1(\DG) \goes{j_*} H_1(\DG/\DE)  \to  \tilde{H}_0(\DE)   \]

is exact, where $j_*$ is induced by the quotient $j: \DG \to \DG'$.

As $\tilde{H}_0(\DE) = 0$, and $H_1(\DE) = 0$, $j_*$ is an isomorphism $H_1(\DG) \cong H_1(\DG')$ as needed.

Finally, we recall the basic idea of Mayer-Vietoris sequences, and use it for several lemmas.
Given spaces $\DA$ and $\DB$ that intersect in $\DC = \DA \cup \DB$, we can often compute the homology of $\DX = \DA \cup \DB$ using the fact that the following sequence is exact.

\begin{align}\label{eq:MV}
\dots \goes{\delta_{n+1}}& H_n(\DC) \goes{\Phi_n} H_n(\DA) \oplus H_n(\DB) \goes{\Psi_n}  H_n(\DX) \goes{\delta_n} %\\ \notag
H_{n-1}(\DC) \goes{\Phi_{n-1}}  \\ \notag
\dots \goes{\Psi_1} H_1(\DX) \goes{\delta_1}&
\tilde{H}_0(\DC) \goes{\Phi_0} \tilde{H}_0(\DA) \oplus \tilde{H}_n(\DB) \goes{\Psi_0} \tilde{H}_0(\DX) \goes{} 0
\end{align}

where $\Psi(\alpha, \beta) = \alpha - \beta$.  See [Hatcher, 2002] p.149; and p. 150 where it states that (<ref>) holds, as given above, for reduced homology.

This lemma, which we use a couple of times,  is nearly obvious.  But being the most simple use of a Mayer-Vietoris sequence, is a useful example.

Let $G$ be a connected graph and $a$ and $b$ be vertices of $G$ at distance at least $4$ apart.
Where $G+E$ is the graph we get from $G$ by adding the edge $E = ab$, $H_1(\DG + \DE) = H_1(\DG) \oplus \ZZ$.
Moreover one gets a basis of $H_1(\DG + \DE)$ from one of $H_1(\DG)$ by adding any cycle $C$ containing
one copy of the edge $E$.

As $a$ and $b$ are distance at least $4$ apart, we make no new triangles by adding $E$.
So by (<ref>) the following is exact.

\[ \to  H_1(\{\bba, \bbb\}) \to H_1(\DG) \oplus H_1(\DE) \goes{\Psi} H_1(\DG + \DE) \to \tilde{H}_0(\{\bba, \bbb\}) \to \tilde{H}_0(\DG) \oplus \tilde{H}_0(\DE) \to  \]

Using $H_1(\{\bba, \bbb\}) = 0$, $H_1(\DE) = 0$ and $\tilde{H}_0(\DG) \oplus \tilde{H}_0(\DE) = 0 \oplus 0 = 0$ we get
a short exact sequence

\[ 0 \to  H_1(\DG) \oplus 0 \goes{\Psi} H_1(\DG + \DE) \goes{\delta} \tilde{H}_0(\{\bba, \bbb\}) \to 0. \]

As $\tilde{H}_0(\{\bba, \bbb\}) = \ZZ$ is free, this splits to give
$H_1(\DG + \DE) = H_1(\DG)  \oplus \tilde{H}_0(\{\bba, \bbb\}) = H_1(\DG) \oplus \ZZ$
as needed.

The statement about the basis comes as follows:
the injection $\Psi$ injects $H_1(\DG)$ as a subgroup
of $H_1(\DG + \DE)$. By exactness, this is exactly the kernel of $\delta$, so
one gets a final basis element of $H_1(\DG + \DE)$ from any cycle that $\delta$ maps onto
the generator $[b-a]$ of $\tilde{H}_0({a,b})$.  This is any cycle made up of a walk in $G$ with boundary $[b-a]$ and a walk in $E$ with boundary $[a-b]$; so any cycle $C$ in $G$ that contains $E$ once.

The following lemma uses the above, with excision to say that we `pinch' a long basis cycle into $2$ cycles, they both become basis cycles, replacing the original cycle in the basis.
This will be used in Step (2) of the construction of the sum gadget.

Let $G$ be a graph, $C$ be a non-contractible cycle in $H_1(\DG)$, and $a$ and $b$
be vertices of $C$ at distance at least $4$ apart. Where $G'$ is the graph we get
from $G$ by identifying $a$ and $b$, $H_1(\DG') = H_1(\DG) \oplus \ZZ$.
Moreover, one gets a basis of $H_1(\DG')$ by taking a basis of $H_1(\DG)$, and doing either of:

* adding one of the new cycles made from $C$ by identifying $a$ and $b$, or

* replacing $[C]$ with the new cycles we get from $C$ by the identification.

Add an edge $E$ between $a$ and $b$. By Lemma <ref> and Lemma <ref> we get

\[ H_1(\DG') = H_1(\DG + \DE) = H_1(\DG) \oplus \ZZ, \]

as needed.

To get a basis of $H_1(\DG + \DE)$ from that of $H_1(\DG)$ we add any cycle containing $E$ once. So we us the cycle $C_1 = P_1 + E$ where $P_1$ is a path in $C$ from $b$ to $a$.  Moreover, where $C = P_2 + P_1$, we have $[C] = [C_2] + [C_1]$, so we get another basis of $H_1(\DG + \DE)$ by removing $[C]$ and adding $[C_2]$.

Under the the contraction of $E$ to $\DG'$, $C_1$ and $C_2$ become the cycles we get from $C$ by identifying $a$ and $b$, as needed.

The following says that if we identify end gadget-cycles of disjoint gadgets then,
assuming that the identified gadget-cycle is in an $\NT$-basis of both gadgets,
our $\NT$-basis in the new graph is the union of the $\NT$-bases of the two gadgets.  (The the identified gadget-cycle only appears once in the new basis.)

Let $F$ and $H$ be disjoint connected graphs and let $C_F$ and $C_H$ be
isomorphic non-contractible $1$-cycles of $F$ and $H$ respectively.
Let $G$ be the graph we get from $F$ and $H$ by identifying $C_F$ and $C_H$.

\[ H_1(\DG)  = (H_1(\DF) \oplus H_1(\DH))/H_1(\DC_\DF).\]

(This is '$=$', not just '$\cong$', so one gets an $\NT$-basis of $G$ from
the union of bases of $F$ and $H$, by removing the repeated basis element $[C_F]$. )

By (<ref>), the sequence

\[ \dots \to H_2(\DG) \goes{\delta} H_1(\DC_\DF) \goes{\Phi} H_1(\DF) \oplus H_1(\DH) \goes{\Psi}
H_1(\DG) \to \tilde{H}_0(\DC_\DF) \to \dots \]

where $\Phi(\alpha) = (\alpha, -\alpha)$,
is exact.

As $\tilde{H}_0(\DC_\DF) = \emptyset$, the map $\Psi$, which is isomorphic on
both $H_1(\DF)$ and $H_1(\DH)$, is surjective. So elements of
$H_1(\DF)$ and $H_1(\DH)$ generate $H_1(\DG)$.

As $C_F$ is non-zero in $H_1(\DG)$ it is not the boundary of anything in $G$,
so $\delta$  maps everything to $0$. Thus by exactness, $\Phi$ is injective,
and the kernel of $\Psi$ is the element $(C_F,-C_F) = (C_F, - C_H)$, identifying
$C_F$ and $C_H$.
$H_1(\DG) = (H_1(\DF) \oplus H_1(\DH))/H_1(\DC_\DF)$,
as needed.

The following two lemmas deal with the situation when we identify two gadget-cycles of a connected graph.  In doing so, one of the identified gadget-cycles, both of which can be assumed to be basis cycles, becomes dependent on the other, so falls out of the basis; at the same time, we create a new basis cycle that we can take to be in $\sT$.

The lemmas work much like Lemmas <ref> and <ref> worked to identify two vertices.
Lemma <ref> adds a new path-of-cycles between the cycles we want to identify, and then Lemma <ref> uses excision to `contract' this path.

We say cycles are independent if they are independent in $H_1(\DG)$.  Note that this
implies they are non-contractible, as the $0$ element is never independent of anything, so in particular, they are not triangles.

Let $A$ and $B$ be disjoint isomorphic independent cycles in a graph $G$.

Let $E$ by a copy of $P_\ell \times A$ for $\ell \geq 4$, and let
$G + E$ be the graph we get by identifying $\{0\} \times A$ in $E$ with $A$ and
$\{\ell\} \times A$ in $E$ with $B$. Let $C$ be any cycle in $G+E$ whose intersection
with $E$ is a path with one endpoint in each of $A$ and $B$.

We have that

\[ H_1(\DG+\DE) = \angles{ (\ccB \setminus \{B\}) \cup \{C\} } \]

for any basis of $H_1(\DG)$ containing $[B]$.

(Note that if $[B]$ is torsion-free, as it will be for us, then $H_1(\DG + \DE) \iso H_1(\DG)$.)

As the intersection of $G$ and $E$ is $A \cup B$, the sequence

\begin{eqnarray*}
% \dots \to  H_2(G+E)
% &\goes{\delta_2}&
\goes{} H_1(\DA \cup \DB) & \goes{\Phi_1} & H_1(\DG) \oplus H_1(\DE)
\goes{\Psi_1}  H_1(\DG+\DE) \\
% &\goes{\delta_1}& H_0(A \cup B) \goes{\Phi_0} H_0(G)\oplus H_0(E) \to \dots
&\goes{\delta_1}& \tilde{H}_0(\DA \cup \DB) \goes{\Phi_0} \tilde{H}_0(\DG)\oplus \tilde{H}_0(\DE) \to \dots
\end{eqnarray*}

from (<ref>), which quickly becomes

\[ \to  H_1(\DA \cup \DB)  \goes{\Phi}  H_1(\DG) \oplus H_1(\DE) \goes{\Psi}  H_1(\DG+\DE)
\goes{\delta} \ZZ \to 0, \]

is exact.

Here $\Phi: \alpha \mapsto (\alpha, -\alpha)$ and
$\Psi: (\alpha, \beta) \mapsto \alpha + \beta$. So we see that, $\Psi(H_1(\DG) \oplus H_1(E)) = \Psi(H_1(\DG) \oplus \{0\})$.
Indeed, $H_1(E)$ has only the one non-zero element $[A] = [B] =: 1$
and so for any $[C] \in H_1(\DG)$,

\[ \Psi( ([C],1) ) = \Psi( [C],[A]) = [C] + [A] = \Psi([C] + [A], 0). \]

Thus the image of $\Psi$ is the image of its restriction $\Psi_r$ to $H_1(\DG) \oplus \{0\}$. To determine this, we observe that the kernel of $\Psi_r$
is, by exactness

\begin{eqnarray*}
\ker(\Psi) \cap ( H_1(\DG) \oplus \{0\}) & = & \img(\Phi) \cap (  H_1(\DG) \oplus \{0\}) \\
& = &  \{ (\sigma, 0) \mid [\sigma] = 0 \mbox{ in } H_1(\DE) \}\\
& = & \angles{( [A - B], 0 )}.
\end{eqnarray*}

So $\Psi_r$, and so $\Psi$, injects $H_1(G) / \angles{A - B}$ into $H_1(G+E)$.
On the other hand, by exactness,  $\delta$ surjects onto $\ZZ$ so has co-rank of $1$, so $H_1(\DG+\DE)/\img(\Psi_r) \iso \ZZ$.  As $Z$ is free, we get

\[ H_1(\DG + \DE) \iso \img(\Psi_r) \oplus \ZZ = \frac{H_1(\DG)}{\angles{A-B}} \oplus \ZZ. \]

The factor $H_1(\DG)/\angles{A-B}$ is generated by the basis $\ccB \setminus \{[B]\}$ and
the factor $\ZZ$ by any cycle $C$ of $G + E$ such that $\delta( C \cap E)$ = $a  + b$, independent of this basis, this is any $C$ made from a walk in $E$ concatenated with a walk in $G$ having the same (but reversed) endpoints.

Let $G$ be a graph and $A$ and $B$ be independent, isomorphic cycles of $G$ being
distance at least $4$ apart. Let $G'$ be the graph we get from $G$ by identifying $A$ and $B$.
Then $H_1(\DG')$ has a basis consisting of any basis of $G$ containing $A$, less the cycle $A$, and $[C]$ where $P$ is a walk from a vertex $a$ in $A$ to a vertex $b$ in $B$ that are identified in $G'$ and $C = P / \{a,b\}$ is we get by identifying $a$ and $b$ in $P$.

Make $G_1$ from $G$ by taking a new a copy $E$ of $P_l \times A$ and
identifying copies of $A$. The basis
does not change. Now make $G_2$ by attaching the other end to $B$.
We get the basis we want by Lemma <ref>.
Now we contract $E$ to a cycle, one edge at a time, using Lemma <ref>
to get $G'$.

This final lemma says that if we `plug' a basis cycle $C$ in a graph with a vertex $v_C$ adjacent to all of its vertices, then $C$ becomes contractible and falls out of the basis.

Let $C$ be a cycle in an $\NT$-basis of $G$, and let $G'$ be the graph we get from $G$ by adding a new vertex $v_C$ adjacent to all vertices in $C$.
Then $H_1(\DG') = H_1(\DG) \setminus \{ [C] \}$.

Let $W$ be the wheel in $G'$ induced by $V(C) \cup \{v_C\}$.  It is easy to see that $H_1(\bbW) = 0$, and so by (<ref>), the sequence

\[ \goes{\delta} H_1(\DC) \goes{\Phi} H_1(G) \oplus 0 \goes{\Psi} H_1(\DG') \to 0 \]

is exact. So $\Psi$ surjects $H_1(\DC)$ onto $H_1(\DG')$. As $H_1(\DC)$ is clearly $\angles{[C]}$, and so the image of $\Phi$ is $\angles{ ([C],0)}$, this is the kernel of $\Psi$.  So

\[ H_1(\DG') \iso H_1(\DG)/\angles{[C]}. \]

§.§ Computing $\NT$-bases of $S_s$ and $\Ga$

In this section we prove Theorem <ref>, which gives us an $\NT$-basis of
$\Ga$.  First we find an $\NT$-basis of the sum gadget $S_s$ constructed in Section <ref>.

For any $s \geq 2$, $S_s$ has an $\NT$-basis consisting of any $s$ of its $s+1$ end gadget-cycles:  $A_0, A_1, \dots A_{s-1}$ and $Z$.

Referring to Construction <ref>, in which we constructed $S_s$, we started with
$\ccP = P_\ell \times \sB$ which by Lemma <ref> has an $\NT$-basis consisting
of either of its end gadget-cycles.

In step (1) we take a quotient of one of these end gadget-cycles by subpaths.  Applying Lemma <ref> one edge at a time, we have that the resulting graph $S_s^{(1)}$ still has an $\NT$-basis consisting of either of its end gadget-cycles.

In step (2) we construct $S_s^{(2)}$ from $\Ga[1]$ by pinching several vertices together in the other end gadget-cycle $0 \times \sB$.  As $0 \times \sB$ can be assumed to be a $\NT$-basis of $S_s^{(1)}$,  we can apply Lemma <ref> each time we do this, and conclude that the resulting cycles $A_0', \dots, A_{s-1}'$ make up an $\NT$-basis of $S_s^{(2)}$.

For each attachment, in step (3), of a path-of-cycles $F = P_1 \times \sC$ to $A_i'$,
we apply Lemma <ref>, with $H$ containing $C_H = A_i'$ as our gadget so far,
to get that $A_i$ can replace $A_i'$ in an $\NT$-basis. Thus the $A_i$ make up an $\NT$-basis of $S_s^{(3)}$.

Lemma <ref> tells us that the end gadget cycle $Z$ is independent of any $s-1$ of these $A_i$, so can replace any one of them in an $\NT$-basis.

We are now ready to prove the main theorem of the section, that $\Ga$ has an
$\NT$-basis consisting of gadget-cycles the cycles from an $\NT$-basis $\ccB_T$ of $\sT$.

In Step (1) of Construction <ref> we introduce a set of $3n+1$ disjoint copies
of $\sC$. Indeed, letting $V(G) = [n]$ and, for $i \in [n]$, letting $\ccB^i = \{ A^i_0, A^i_1, A^i_2 \}$, we introduce the set

\[ \ccB := \bigcup_{i \in [n]} \ccB^i  \cup \{ \sZ \} \]

of copies of $\sC$.

In Step (2) we construct a graph $\Ga[2]$, the end gadget-cycles of which are the cycles in the set $\ccB$, as follows. We start with a copy $G_1:= S^1_3$ of $S_3$ and rename its copy of $Z$ as $\sZ$.   For $i = 2, \dots, n$, we construct $G_i$ from $G_{i-1}$ by taking a new copy $S^i_3$ of $S_3$ and identifying its copy of $Z$ with $\sZ$.  The resulting $G_n$ is $\Ga[2]$.

Now, by Lemma <ref>, we can assume that the copy of $Z$ is in an $\NT$-basis of each $S^i_3$, so applying Lemma <ref> when we construct $G_{i+1}$ from $G_i$ we get an $\NT$-basis of
$G_{i+1}$ by adding any two of the cycles in $\ccB^{i+1}$ to our $\NT$-basis of $G_i$.  It follows that for any choice of two cycles in $\ccB^i$ for each $i$, there is an $\NT$-basis of $\Ga[2]$ containing these cycles.
At this point $\sT$ is still a tree, so has an empty $\NT$-basis $\ccB_T$.  The following statement is therefore true:

For any two cycles $C, C'$ in $\ccB$ there is an $\NT$-basis $\ccB^*$ of $\Ga[2]$ with

\begin{equation}\label{eq:basis} \{C, C'\} \cup \ccT \subset \ccB^* \subset \ccB \cup \ccB_T. \end{equation}

In Steps (3) and (4) we construct $\Ga$ from $\Ga[2]$ by taking several new copies of $S_2$ and attaching them to $\Ga[2]$ by identifying their copies of $A_0$ and $A_1$ with cycles of $\Ga[2]$ in $\ccB$. Applying the following claim each time we do this, we add a new cycle of $\sT$ to $\ccB_T$ and verify that (<ref>) holds for the newly constructed graph in place of $\Ga[2]$.  Thus the theorem is proved with the following claim.

Let $G$ be a graph and $C$ and $C'$ be disjoint copies of $\sC$ in an $\NT$-basis $\ccB$ of $G$.  Let $T$ be a connected subgraph of $G$ with one vertex in each of $C$ and $C'$.  Let $G'$ be the graph we get from $G$ and a disjoint copy $S$ of $S_2$ by identifying $C$ with $A_0 \leq S$ and $C'$ with $A_1 \leq S$ in such a way that the tree $T(S)$ of $S$ has one leaf identified with the vertex of $T$ in $C$ and one other leaf the vertex of $T$ in $C'$.  Let $T'$ be the union of $T$ and $T(S)$.

Where $\ccB_T$ is an $\NT$-basis of $T$, there is a cycle $C_T$ in $T'$ such that

* $\ccB_T \cup \{C_T\}$ is an $\NT$-basis of $T'$, and

* $\ccB \cup \{C_T\}$ is an $\NT$-basis of $G'$.

Starting with $G$ and the copy $S$ of $S_2$, first identify $A_0$ in $S$ with the cycle $C$ of $G$.
Call this graph $G^{(1)}$.
By Lemma <ref>, we get an $\NT$-basis $\ccB^{(1)}$ of $G^{(1)}$ by removing $C$ from $\ccB$ and adding the cycles $A_1$ and $Z$ of $S$.  The $\NT$-basis of $T$ has not changed, as we have just attached a tree $T(S)$ to some vertex.

Now construct $G'$ by identifying the cycles $A_1$ and $C'$ of $G^{(1)}$.  This makes $T'$ by identifying vertices of
$T$ that are distance at least $4$ apart, so by Lemma <ref> creates a new cycle $C_T$ in $T'$ such that
$\ssB_T \cup \{C_T\}$ is an $\NT$-basis of $T'$.
By Lemma <ref>, we can get an $\NT$-basis of $G'$ from $\ccB^{(1)}$ by removing the cycle $C'$ and adding the cycle $C_T$.  This basis contains $Z$ and $A_1$ of $S$. But in $S$, the cycles $Z, A_1,$ and $A_0$ are minimally dependent,
so we can replace $Z$ with $A_0 = C$ in this basis, getting that $\ccB \cup \{C_T\}$ is an $\NT$-basis of $G'$.

As mentioned before the claim, this completes the proof of the theorem.

§ THE FULL CONSTRUCTION

Now we can finish our construction of the instance $\Gb$ of $\NF(\sH)$ for an instance $G$ of $3$-colouring.

For a graph $G$, let $\Ga$, with subgraph $\sT$,  be given by Construction <ref>.
By Theorem <ref>, $\Ga$ has an $\NT$-bases consisting of gadget cycles and cycles from a
basis $\ccB_T$ of $\sT$.  Construct the graph $\Gb$ from $\Ga$ by adding, for
each cycle $C$ in $\ccB_T$, a new vertex $v_C$,  and edges from $v_C$ to each vertex of $C$.

The following is an immediate corollary of Theorem <ref> by Lemma <ref>.

For a graph $G$, the graph $\Gb$ constructed from $\Ga$ in Construction <ref> has an $\NT$-basis consisting of end gadget-cycles of $\Gb$.

At last, we prove our main technical result, Theorem <ref>, which says that for a reflexive graph $\sH$ non-trivial first homology, the problem $\NF(\sH)$ is $\NP$-hard.

For an irreflexive instance $G$ of $3$-colouring, let $\Gb$ be the graph from Construction <ref>. We show that $G$ is $3$-colourable if and only if $\Gb$ has a non-flat homomorphism to $\sH$.

Indeed, assume there is a non-flat $\sH$-colouring $\phi$ of $\Gb$.  So for some cycle $C$ of $\Gb$ we have $[\phi(C)] \neq 0$, and by Corollary <ref> we many assume that $C$ is a end gadget-cycle of $\Gb$, and so of $\Ga$. Restricting $\phi$ to $\Ga$ we get by Lemma <ref> that $\phi(\sZ)$ is non-trivial, and so by Lemma <ref> there is a $3$-colouring of $G$.

On the other hand, assume that there is a $3$-colouring of $G$. By Lemma <ref> there is a non-flat $\sH$-colouring $\phi$ of $\Ga$ which we may assume is $0$ on $\sT$.  Setting $\phi(v_C) = 0$ for every $C \in \ccB_T$ extends this to a non-flat $\sH$-colouring  of $\Gb$.

This completes the proof of Theorem <ref> and so,
as shown in Section <ref>, of Theorem <ref>.

§ THE PROBLEM FOR TRIANGLE FREE $H$

This is not as trivial as I thought.

For a triangle free reflexive graph $H$, a homomorphism $\phi:G \to H$ is flat if for all cycles $B$ of $G$, we have $[\phi(B)] = 0$ in $H_1(\DH)$.  We can thus extend our defintion of the problem of non-flat $C$-colourings, to triangle free reflexive graphs $H$.

Problem: $\NF(H)$

Instance: A graph $G$.

Question: Is there a non-flat homomorphism of $G$ to $H$.

* As [Lee et al., 2021] gives a polynomial non-mixing certificate, $\Mix(H)$ is $\coNP$-complete so we just have to show it is $\coNP$-hard

* It is enough to show that $\NF(H)$ is $\NP$-hard: there are always flat homomorphisms, and by [Lee et al., 2021] flat homomorphisms are all in the same component.  So $G$ is a yes instance of $\Mix(H)$ if it is a no instance of $\NF(H)$ and is a no instance of $\Mix(H)$ it is is a yes instance of $\NF(H)$.

I thought this was trivial, if we can prove it we have that $\NF(H)$ is $\NP$-hard, as needed.

Let $C$ be a shortest cycle in $H$. For an instance $G$ of $3$-colouring, let $\Gb$ be the instance of $\NF(C)$ constructed in Construction <ref>.
There is a non-flat $C$-colouring of $\Gb$ if and only if there is non-flat $H$-colouring of $\Gb$.

On direction is truly trivial: that a non-flat $C$-colouring yields a non-flat $H$-colouring is trivial.

On the other hand, assume we have a non-flat $H$-colouring $\phi$ of $\Gb$.
There is some cycle $B$ of $\Gb$ such that $\beta := [\phi(B)] \neq 0$ in $H_1(H)$.

Without formal proof, the main ideas are:

* $B$ may be assumed to be in any $\NT$-basis of $\Gb$, so to be an end gadget-cycle.
( So we need to prove fact <ref> for homology.  This shouldn't be hard, but requires some definitions. )

* By girth, this allows us to say that $\beta$ is some copy of $C$ in $H$.

* All end gadget cycles $B'$ have $[\phi(B') \in \{ C, -C , 0\}$ and the sum gadget works for them.
( So all our gadget constructions are about homology not wind.  I think there is nothing difficult in this extension beyond

* We should be able then to force every vertex of $\phi(\Gb)$ down onto $C$, but this is maybe non-trivial to do.
(Actually, not so hard, we can build it into the constructions like we did with the assumption that $T$ maps to $0$. )
At this point, it seems like we have to do the constructions for homology rather than wind anyways, so we should do it all in one go.

Another approach might be to add new gadgets that force every vertex of $\Gb$ to map to $C = \phi(B)$, we can do this with more
paths-of-cycles.  But then we have also to plug the new holes.  This doesn't seem too hard.  Actually it does. It is hard to do this without introducing new vertices that can't wander off $C$.

Shit.  I don't see anyway around this.  It is the right way to do it though.

What are the bits we need.

* The definition of flat above.  So we have to define homology before we do it.

* We must show that adjacent cycles in $\Hom(C,H)$ have the same homology in

* We must show that under a homomorphsim $\phi: P_\ell \times B \to C$ the end gadget-cycles of a path of cycles are mapped to homologous cycles in $H_1(H)$.
Probably observe that two cycles are adjacent in $\Hom(C,H)$ if and only if there is a
$\phi: P_1 \times C \to H$ taking one end cycle to each of them.  It then follows from previous point.

* Wind in the sum gadget and everything else has to be replaced by homology versions.

* THat's it for technical stuff I think. But there must be a lot of re-arranging.
As the homology defintion has to come earlier now.
Should the outline still be for cycles?  It is somehow easier to understand.

This construction should work to show that $\NF(H)$ is $\NP$-hard for any $H$ with a non-contractible cycle.   But the reductions to $\Mix(H)$ would need an analogue of [Lee et al., 2021] that we known need not hold for all such $H$.

The $\NF(H)$ hardness should even hold all $H$ with non-trivial homotopy, but by Hurewitz, these are the same as or graphs are connected.  It should also hold for any $H$ for which $\Hom(C,H)$ is disconnected for some $C$ of girth at least $5$. But we should be able to show this afterwards by using the cycle to define a subalgebra.
Probably non-trivial higher homology can yield similar hardness results, but that seems nasty.

Remember for all of these $H$ there is a cycle-term proof that $\Hom(H)$ is $\NP$-complete. This might be a nice place to include that proof.

( Emphasise that [Lee et al., 2021] is used in two places.  To put us in $\coNP$, and to show that
if there are no non-flat $H$-colourings, then we mix.

§  OTHER THINGS TO MAYBE MENTION IN THE PAPER

§.§ Weight

Mix is maybe usually sometimes defined for the colour graph rather than the hom graph.  In the introduction we should observe that these are equivalent.

§.§ Irreflexive

If $C$ is odd, then $G$ can only have flat maps if it is bipartite.
But if there is a non-flat map, the non-mixing comes from the 'reverse' map.

So for odd $C$ $\Mix(C)$ is just $\Hom(C)$ for non-bipartite instances.
If there is a map it wraps something and so we cannot get to the map we get by
reversing direction.  If it doesn't map, then $\Hom(G,C)$ is trially connected.

(SO this is why Ben restricted to the bipartite instances– to make it interesting.)
So we make bipartite instances. They are non-flat if we wrap twice.
What does this do to our netting?  We can make it
with girth $g-1$-cycles (but then for $g = 5$ our gadget needs loops).

For even $C$ we don't do girth $4$ and we can use $g-2$ netting for everything else.

§.§ Restricted classes for $G$ in which $\Mix(H)$ is trivial

From <cit.> we have that if a graph $G$ has no map to $C$
(symmetric reflexive girth $g$) in which any cycle gets wind other than $0$,
then mixing is trivial as $\Col(G,C)$ is connected.

What graphs have this property?  Certainly chordal graphs
( or topologically $1$-connected graphs) do.  What else.
Jae-baek talks of shortcuts.

A cycle in a graph $G$ is  isometric if the distance between any
two vertices in the cycle is the distance in between them in $G$.
( If it isn't isometric, then it has a shortcut between the vertices
that violate this. )
If there are no isometric cycles of girth at least $g$ then there can
be no maps to $C$ with wind other than one on a cycle. Indeed, towards
contradiction, let $B$ be the smallest violating cycle: it has wind
$1$ and there is a shortcut between $x$ and $y$. Let $P$ and
$Q$ be the two paths between $x$ and $y$ in $B$ and let $S$ be the
shortcut. Then $S$ makes a cycle with $P$ and another with $Q$, one of
them must have wind $1$, and it has smaller girth than $B$.
By choice of $B$, this cycle does not violate, and so has no shortcuts.   But as it has wind $1$ is has girth greater than $g$ so must have

So graphs with no isometric cycles of girth $g$ or greater are

We wondered if this is a characterisation of $C$-mixing graphs.

No:  Take $C \times P$ where $P$ is a long path, and then taper on
end.  We have lots of girth $g$ isometric cycles, but the all
of them are homotopic to the tapered one, so get wind $0$.

This example gives us the idea for our gadget, from which we get our main constructions.

[1]
R. Brewster and B. Moore.
Characterizing circular colouring mixing for $p/q<4$.

[Brewster and Noel, 2015]
R. Brewster and J. Noel.
Mixing homomorphisms, recolorings, and extending circular
J. Graph Theory, 800 (3):0 173–198, 2015.

[Brewster et al., 2021]
R. Brewster, J. Lee, and M. Siggers.
Reconfiguration of homomorphisms to reflexive digraph cycles.
Discrete Mathematics, 3440 (8):0 112441, 2021.

[Brightwell and Winkler, 2000]
G. Brightwell and P. Winkler.
Gibbs measures and dismantlable graphs.
JTCB, 780 (1):0 141–166, 2000.

[Bulatov, 2017]
A. Bulatov.
A dichotomy theorem for nonuniform CSPs.
In 58th Annual IEEE Symposium on Foundations of
Computer Science—FOCS 2017, pages 319–330. IEEE Computer Soc., Los
Alamitos, CA, 2017.

[Cereceda et al., 2009]
L. Cereceda, J. van den Heuvel, and M. Johnson.
Mixing 3-colourings in bipartite graphs.
European J. Combin., 300 (7):0 1593–1606,

[Gopalan et al., 2009]
P. Gopalan, P. Kolaitis, E. Maneva, and C. H. Papadimitriou.
The connectivity of Boolean satisfiability: computational and
structural dichotomies.
SIAM J. Comput., 380 (6):0 2330–2355, 2009.

[Hatcher, 2002]
A. Hatcher.
Algebraic topology.
Cambridge University Press, Cambridge, 2002.

[Lee et al., 2020]
J. Lee, J. Noel, and M. Siggers.
Reconfiguring graph homomorphisms on the sphere.
European J. Combin., 86:0 103086, 21, 2020.

[Lee et al., 2021]
J. Lee, J. Noel, and M. Siggers.
Recolouring homomorphisms to triangle-free reflexive graphs, 2021.

[van den Heuvel, 2013]
J. van den Heuvel.
The complexity of change.
In Surveys in combinatorics 2013, volume 409 of London
Math. Soc. Lecture Note Ser., pages 127–160. Cambridge Univ. Press,
Cambridge, 2013.

[Wrochna, 2015]
M. Wrochna.
Homomorphism reconfiguration via homotopy.
In 32nd International Symposium on Theoretical Aspects
of Computer Science, volume 30 of LIPIcs. Leibniz Int. Proc.
Inform., pages 730–742. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern,

[Zhuk, 2020]
D. Zhuk.
A proof of the CSP dichotomy conjecture.
J. ACM, 670 (5):0 Art. 30, 78, 2020.