the minimum element, the associated functor homology ${\rm
H}_{i}(\mathbf{P}({\tt G})\setminus\\{\emptyset\\};\mathcal{F}_{R,R})$ is not.
In fact, the functor homology groups ${\rm H}_{i}(\mathbf{P}({\tt
G})\setminus\\{\emptyset\\};\mathcal{F}_{R,R})$ and the multipath cohomology
groups $\mathrm{H}_{\mu}^{i+1}({\tt G};R)$ are related, for $i\geq 2$, by the
standard universal coefficients theorem. The induced short exact sequence

$0\to\mathrm{Ext}^{1}_{R}({\rm H}_{i-1}(\mathbf{P}({\tt
G})\setminus\\{\emptyset\\};\mathcal{F}_{R,R}))\to\mathrm{H}_{\mu}^{i+1}({\tt
G};R)\to\mathrm{Hom}_{R}({\rm H}_{i}(\mathbf{P}({\tt
G})\setminus\\{\emptyset\\};\mathcal{F}_{R,R}))\to 0$

features an $\mathrm{Ext}$ functor, which is non trivial in general. For
instance, taking $A=R=\mathbb{Z}$, the multipath cohomology of the bipartite
complete graph ${\tt K}_{5,5}$ has $3$-torsion ([CCC22, Proposition 4.5]).

The connection shown in the previous example between functor homology and
multipath cohomology is given by two facts; the first, that functor
(co)homology of a category, for nice functors, agrees with the usual
(co)homology of the classifying space (with local coefficients as in [Qui78,
Section 7]), and the second, that the classifying space of the opposite
category is naturally homeomorphic to the classifying space of the category
itself. As shown in Remark 6.9, multipath cohomology and functor cohomology
agree (in degree $i\geq 2$) when we pass to the opposite category associated
to the path poset. Then, in the Turner-Wagner approach, which uses functor
homology, one computes the higher colimits of $\mathcal{F}$, whereas multipath
cohomology provides a way to compute the higher limits of
$\mathcal{F}\circ\mathrm{op}$; when $\mathcal{F}$ is a coefficient system in
the sense of Quillen, as in the case of constant functors, higher limits and
colimits are computed as usual cohomology on the classyfing spaces; then, as
the $\mathrm{op}$ functor does not change the homotopy type of the classifying
spaces, the assertion follows. Note that this does not provide a precise
relation for non-local coefficients (e.g. $\mathcal{F}_{A,M}$,
$A\neq\mathbb{K}$). In particular, this reasoning does not provide a precise
relationship between Turner-Wagner and multipath cohomologies.

######  Remark 6.11.

All said above provides an alternative way to define multipath cohomology;
i.e., after passing to the path poset and removing the minimum, one can take
the opposite associated category and compute (equivalently) either the higher
limits of $\mathcal{F}_{A,M}$ or the associated cellular cohomology groups (as
the obtained poset is now cellular). However, functor and cellular
cohomologies are not directly computable from the definitions, whereas poset
homology happens to be quite computable, also algorithmically. The approach
has shown to be fruitful in computing the multipath cohomology of all linear
graphs – cf. [CCDT21].

To conclude the comparisons, we point out that, in special cases, like the
linear graph ${\tt I}_{n}$ and the polygonal graph ${\tt P}_{n}$ the
difference between the multipath and the Turner-Wagner homologies is
controlled. This is also due to the fact that both homologies provide roughly
the same amount of information as the chromatic homology – see [ET09, TW12]
for relations between $TW$ and the chromatic homology. In the next subsection
we recall the definition of the latter homology, and prove a comparison result
for the graphs ${\tt I}_{n}$ and ${\tt P}_{n}$.

##  7\. Comparison with chromatic homology

In this section we compare multipath cohomology with chromatic homology of
unoriented graphs [HGR05, Prz10]. The latter can be seen as a special case of
the construction in Section 3; in light of this observation, we can interpret
multipath cohomology as an extension of chromatic homology to the directed
setting.

In the first subsection, we briefly revise the construction of the chromatic
homology (both in its original version [HGR05] and in Przytycki’s variant
[Prz10]). We argue that the multipath cohomology of a graph differs from
either of these theories computed for the underlying unoriented graph. This
uses the fact that multipath cohomology is sensible to orientations.
Nonetheless, in the special case of coherently oriented polygonal graphs and
linear graphs, we prove that the two (co)homology theories contain the same
amount of information – cf. Theorem 7.4. As a consequence, see Corollary 7.6,
we obtain that the multipath cohomology of the coherently oriented polygon
recovers (a truncated version of) the Hochschild homology of its coefficients.
As an application of the functoriality, in the second subsection we clarify
the relationship between multipath cohomology and chromatic homology,
providing the long exact sequence relating multipath and chromatic
cohomologies.

###  7.1. Chromatic homologies

In this subsection we review the construction of two graph homology theories.
The first of these homologies goes under the name of chromatic homology and
was introduced by Helme-Guizon and Rong [HGR05]. The second homology is a
variation of the chromatic homology, and it is due to Przytycki [Prz10].

Let $\tt{G}$ denote a unoriented graph with ordered edges and a base vertex
$v_{0}$. Let $A$ be a commutative unital $R$-algebra, and $M$ be an
$(A,A)$-bimodule. Assume that the $A$-action on $M$ is symmetric – that is
$a\cdot m=m\cdot a$ for all $m\in M$ and $a\in A$. To each spanning sub-graph
$\tt{H}\in SSG({\tt G})$ we associate the module

$M({\tt H})=M\otimes\bigotimes_{c\ \not\ni\ v_{0}}A_{c}\ ,$

where $c$ ranges among the connected components of $\tt H$ – ordered
arbitrarily. If $\tt{H}\prec\tt{H^{\prime}}$ then ${\tt H}\cup
e=\tt{H^{\prime}}$, for some edge $e$. We can define a map ${\tt d}_{{\tt
H}\prec{\tt H^{\prime}}}\colon M({\tt H})\to M({\tt H^{\prime}})$ (cf.
[HGR05]). There are two cases to consider depending on the number of
components merged by $e$;

  * (i)

the edge $e$ is incident into two distinct components of $\tt H$. We have a
natural identification of the components of $\tt H$ and $\tt H^{\prime}$ that
do not share vertices with $e$. Furthermore, precisely two distinct
components, say $c_{1}$ and $c_{2}$, of $\tt H$ are merged into a single
component of $\tt H^{\prime}$, say $c^{\prime}$. The map ${\tt d}_{{\tt
H}\prec{\tt H^{\prime}}}\colon M({\tt H})\to M({\tt H^{\prime}})$ is defined
as the identity on all factors, but those corresponding to $c_{1}$ and
$c_{2}$, where it behaves as follows

$A_{c_{1}}\otimes A_{c_{2}}\to A_{c^{\prime}}:\ a\otimes b\mapsto ab=ba$

or, if $c_{3-i}$ for $i\in\\{1,2\\}$ contains the marked vertex,

$M\otimes A_{c_{i}}\to A_{c^{\prime}}:\ a\otimes b\mapsto a\cdot b\ ;$

  * (ii)

the edge $e$ is incident to a single component of $\tt H$. There is a natural
identification of all components of $\tt H$ and $\tt H^{\prime}$, and the map
${\tt d}_{{\tt H}\prec{\tt H^{\prime}}}\colon M({\tt H})\to M({\tt
H^{\prime}})$ is taken to be the corresponding identification of the
associated modules.

Similarly, Przytycki (cf. [Prz10]) defines the map $\widehat{\tt d}_{{\tt
H}\prec{\tt H^{\prime}}}\colon M({\tt H})\to M({\tt H^{\prime}})$ as above,
but setting it to be the zero map instead of the identity in case (ii). The
cochain complexes

$({C}^{*}_{\rm Chrom}({\tt G};A,M),{\tt
d}^{*})\quad\text{and}\quad(\widehat{C}^{*}_{\rm Chrom}({\tt
G};A,M),\widehat{\tt d}^{*})\ ,$

are defined as follows:

${C}^{i}_{\rm Chrom}({\tt G};A,M)=\widehat{C}^{i}_{\rm Chrom}({\tt
G};A,M)=\bigoplus_{\tiny\begin{matrix}{\tt H}\subset{\tt G}\\\ \\#E({\tt
H})=i\end{matrix}}M({\tt H})\ ,$

and, for $x\in M({\tt H})$,

${\tt
d}(x)=\sum_{\tt{H}\prec\tt{H^{\prime}}}(-1)^{\zeta(\tt{H}\prec\tt{H^{\prime}})}{\tt
d}_{{\tt H}\prec{\tt H^{\prime}}}(x)\qquad\text{and}\qquad\widehat{\tt
d}(x)=\sum_{\tt{H}\prec\tt{H^{\prime}}}(-1)^{\zeta(\tt{H}\prec\tt{H^{\prime}})}\widehat{\tt
d}_{{\tt H}\prec{\tt H^{\prime}}}(x)\ ,$

where $\zeta$ is defined as:

(9) $\zeta({\tt H}\prec{\tt H}\cup e)=\begin{cases}0&\text{if an even number
of edges preceding }e\text{ belong to }{\tt H}\text{,}\\\
1&\text{otherwise.}\end{cases}$

######  Remark 7.1.

The chain complexes $({C}^{*}_{\rm Chrom}({\tt G};A,M),{\tt d}^{*})$ and
$(\widehat{C}^{*}_{\rm Chrom}({\tt G};A,M),\widehat{\tt d}^{*})$ do not depend
on the ordering of the edges up to isomorphism – see [HGR05, Prz10].

Recall that ${\tt I}_{n}$ denotes the $n$-step graph in Figure 1, and ${\tt
P}_{n}$ denotes the polygonal graph in Figure 2.

######  Remark 7.2.

In the special case of the coherently oriented line graph ${\tt I}_{n}$ and of
the polygon ${\tt P}_{n}$, the cochain complexes $({C}^{*}_{\rm Chrom}({\tt
G};A,M),{\tt d}^{*})$ and $(\widehat{C}^{*}_{\rm Chrom}({\tt
G};A,M),\widehat{\tt d}^{*})$ can be extended, using the orientation of ${\tt
I}_{n}$ and of ${\tt P}_{n}$, to the non-commutative context – cf. [Prz10,
Remark 2.3 (ii)] – and this extension is perfectly identical to our definition
of $\mu$ – cf. subsection 4.1.

Observe that the chromatic homology theories can be recovered from the
framework in Section 3.1.

######  Remark 7.3.

Consider an unoriented graph ${\tt G}$ and the poset $P=SSG({\tt G})\supseteq
P({\tt G})$. Recall that $\mathbf{P}$ denotes the category associated to $P$.
Consider the covariant functor $\mathcal{F}\colon\mathbf{P}\to
R\text{-}\mathbf{Mod}$ defined by extending the functor
$\mathcal{F}_{A,M}\colon\mathbf{P}({\tt G})\to R\text{-}\mathbf{Mod}$, cf.
Equation (7), to the whole $SSG({\tt G})$. This extension is defined as
follows: when the covering relation ${\tt H}\prec{\tt H}^{\prime}$ is as in
case (ii) above, $\mathcal{F}$ is either the identity or the $0$-map,
depending whether we want to recover $({C}^{*}_{\rm Chrom}({\tt G};A,M),{\tt
d}^{*})$ or $(\widehat{C}^{*}_{\rm Chrom}({\tt G};A,M),\widehat{\tt d}^{*})$.
These constructions do not depend on signs by Corollary 3.18.

The following theorem establishes a first relation between multipath and
chromatic (co)homologies.

######  Theorem 7.4.

Let $A$ be a unital $R$-algebra, and $M$ an $(A,A)$-bimodule. Then, we have
the following isomorphisms of chain complexes (of $R$-modules):

(10) $(C^{*}_{\mu}({\tt I}_{n};A,M),d)\cong(\widehat{C}^{*}_{\rm Chrom}({\tt
I}_{n};A,M),\widehat{\tt d})\cong({C}^{*}_{\rm Chrom}({\tt I}_{n};A,M),{\tt
d})$

and

(11) $(C^{*}_{\mu}({\tt
P}_{n};A,M),d)\oplus(M[n+1],0)\cong(\widehat{C}^{*}_{\rm Chrom}({\tt
P}_{n};A,M),\widehat{\tt d})\ ,$

where $(M[n+1],0)$ is the cochain complex consisting of a copy of $M$ in
degree $n+1$.

###### Proof.

By Remark 7.2, the cochain complexes $({C}^{*}_{\rm Chrom}({\tt G};A,M),{\tt
d}^{*})$ and $(\widehat{C}^{*}_{\rm Chrom}({\tt G};A,M),\widehat{\tt d}^{*})$
can be defined for arbitrary unital $R$-algebras, using the orientation of the
coherently oriented $n$-step graph ${\tt I}_{n}$ or the polygon ${\tt P}_{n}$.
The proof follows directly from Remark 7.3 by noticing that $SSG({\tt
I}_{n})=P({\tt I}_{n})$ and $SSG({\tt P}_{n})$ is the poset $P({\tt
P}_{n})\cup\\{{\tt P}_{n}\\}$ obtained from the path poset $P({\tt P}_{n})$ by
adding the ${\tt P}_{n}$ as the maximum. ∎

######  Corollary 7.5.

Let $A$ be a unital $R$-algebra, and $R$ a principal ideal domain. Then, for
all $n\in\mathbb{N}$, we have $\mathrm{H}^{i}_{\mu}({\tt I}_{n};A)=0$, for all
$i\in\mathbb{N}\setminus\\{0\\}$, and

$\mathrm{rank}_{R}(\mathrm{H}^{0}_{\mu}({\tt
I}_{n};A))=\begin{cases}\mathrm{rank}_{R}(A)(\mathrm{rank}_{R}(A)-1)^{n}&n>0,\\\
\mathrm{rank}_{R}(A)&n=0.\end{cases}$

###### Proof.

By Theorem 7.4, Equation (10), the statement follows directly from [Prz10,
Lemma 3.3]. ∎

For a unital $R$-algebra $A$ and an $(A,A)$-bimodule $M$, denote by
$\mathrm{HH}_{*}(A,M)$ the _Hochschild homology_ of $A$ with coefficients in
the bimodule $M$ – see, for instance, [Lod98, Section 1.1.3] for the
definition. Let $\widehat{\mathrm{H}}^{*}_{\rm Chrom}({\tt G};A,M)$ denote the
homology of the complex $(\widehat{C}^{*}_{\rm Chrom}({\tt
G};A,M),\widehat{\tt d})$. We conclude the section showing that the multipath
cohomology groups of the polygon agree with the Hochschild homology of $A$
with coefficients in the bimodule $M$:

######  Corollary 7.6.

Let $A$ be a flat unital $R$-algebra, and $M$ an $(A,A)$-bimodule and let
${\tt P}_{n}$ be the polygon (cf. Figure 2). Then, we have the following chain
of isomorphisms of homology groups:

$\mathrm{H}_{\mu}^{i}({\tt P}_{n};A,M)\cong\widehat{\mathrm{H}}_{\rm
Chrom}^{i}({\tt P}_{n};A,M)\cong\mathrm{HH}_{n-i}(A,M),\quad\text{for
}i=1,...,n.$

###### Proof.

The result follows directly from [Prz10, Theorem 3.1] and Theorem 7.4,
Equation (11). ∎

######  Remark 7.7.

By [TW12, Theorem 1], we have that $TW_{i}({\tt
P}_{n};A,M)\cong\widehat{\mathrm{H}}_{\rm Chrom}^{n-i}({\tt P}_{n};A,M)$ for
$i$ in the set $\\{1,...,n\\}$. From which it follows the isomorphism with the
multipath cohomology in this case.

We conclude this section by remarking that in general the chromatic and the
multipath homologies are distinct, also in the case where $A$ is commutative.

######  Proposition 7.8.

The cohomologies ${\rm H}_{\rm Chrom}$ and ${\rm H}_{\mu}$ are not isomorphic.

###### Proof.

The multipath homology of the non-coherent $3$-step graph is different from
the homology of ${\tt I}_{3}$. Since the chromatic homology does not
distinguish orientations the statement follows. ∎

###  7.2. Short exact sequences and chromatic homology

Here we apply the machinery developed in Section 5 to obtain a long exact
sequence featuring both multipath and chromatic homologies. This clarifies the
relationship between the two homology theories. As an application we recover
the isomorphisms in the case of the linear graph and polygonal graph, when $A$
is a commutative $R$-algebra.

For an oriented graph ${\tt G}$, let $\widehat{C}^{*}_{\rm Chrom}({\tt G};A)$
be the chromatic cochain complex of the underlying unoriented graph. From the
results in the previous section, it follows immediately:

######  Proposition 7.9 (Proposition 1.5).

Let ${\tt G}$ be an oriented graph, and let $A$ be a commutative $R$-algebra.
Then, we have the following short exact sequence of complexes

$0\to\widetilde{C}_{\mu}({\tt G};A)\ {\longrightarrow}\widehat{C}_{\rm
Chrom}({\tt G};A)\longrightarrow C_{\mu}({\tt G};A)\to 0$

where we set

$\widetilde{C}_{\mu}({\tt G};A)\coloneqq C_{\mathcal{F}_{A,A}}(SSG({\tt
G})\setminus P({\tt G}))\left[-\min_{x\in SSG({\tt G})\setminus P({\tt
G})}\\{\ell(x)\\}\right]$

and we extended $\mathcal{F}_{A,A}({\tt H}\prec{\tt H}\cup e)$ to be zero if
the number of components of ${\tt H}$ and ${\tt H}\cup e$ is the same.

###### Proof.

Fix a graph ${\tt G}$ and consider $\mathcal{F}\colon{\bf SSG}({\tt G})\to{\bf
A}$. Following the proof of Proposition 5.11 almost verbatim, we obtain that:
if $P$ is a downward closed sub-poset of $SSG({\tt G})$, then we have the
following short exact sequence of chain complexes

$0\to C_{\mathcal{F}_{|SSG({\tt G})\setminus P}}(SSG({\tt G})\setminus
P)\left[-\min_{x\in SSG({\tt G})\setminus
P}\\{\ell(x)\\}\right]{\longrightarrow}C_{\mathcal{F}}(SSG({\tt
G}))\longrightarrow C_{\mathcal{F}_{|P}}(P)\to 0$

where the sign assignments are induced by any sign assignment on $SSG({\tt
G})$. The statement now follows by taking $P=P({\tt G})$ and
$\mathcal{F}=\mathcal{F}_{A,A}$. ∎

As a consequence we (partially) recover one of the main results of this paper:

######  Corollary 7.10.

Let $A$ be a commutative unital $R$-algebra. Then, we have the following
isomorphisms of chain complexes (of $R$-modules):

(12) $(C^{*}_{\mu}({\tt I}_{n};A),d)\cong(\widehat{C}^{*}_{\rm Chrom}({\tt
I}_{n};A),\widehat{\tt d})\cong({C}^{*}_{\rm Chrom}({\tt I}_{n};A),{\tt d})$

and

(13) $(C^{*}_{\mu}({\tt P}_{n};A),d)\oplus(A[n+1],0)\cong(\widehat{C}^{*}_{\rm
Chrom}({\tt P}_{n};A),\widehat{\tt d}),$

where $(A[n+1],0)$ indicates the cochain complex consisting of a copy of $A$
in degree $n+1$.

###### Proof.

It is sufficient to notice that the poset $SSG({\tt G})\setminus P({\tt G})$
is either empty (if ${\tt G}={\tt I}_{n}$) or a single point (if ${\tt G}={\tt
P}_{n}$). The corollary is an immediate consequence of Proposition 1.5. ∎

##  8\. Open questions

In this section we gather some open questions.

######  Question 8.1 (Full functoriality).

We have shown in Subsection 5 that multipath cohomology is a bifunctor when
restricting either to the category of rings or to the category of graphs with
same number of vertices. Is it possible to lift this result simultaneously to
the full categories $\mathbf{Digraph}$ of directed graphs and
$R$-$\mathbf{Alg}$ of $R$-algebras? If not, what are the obstructions to this
extension?

######  Question 8.2 (Cyclic homology theories and extensions).

One of the main properties of ${\rm H}_{\mu}(-;A)$ (for a fixed $A$) is that
it recovers (a truncation of) the Hochschild homology of $A$. To the best of
the authors’ knowledge, it is still open a question by [Prz10] whether or not
it is possible to recover, in a similar fashion, also the cyclic homology
groups of $A$ – see [Lod98] for the definition. Moreover, the construction in
Section 3.1 can be generalised, by application of the nerve functor and a
suitable adaptation, to the realm of $\infty$-categories – cf. [Lur09]. In
particular, this generalisation should hold for functors in the module
categories over commutative ring spectra. A topological enhancement of the
cyclic homology theories is given by the so-called _topological Hochschild
homology_ (or _topological cyclic homology_) – cf. [NS18]. Do we have for
topological Hochschild homology, cyclic homology, negative homology, or
periodic homology, a result similar to Proposition 1.4?

######  Question 8.3 (Categorification of graph invariants).

The chromatic homology is named after the chromatic polynomial, which can be
obtained as the graded Euler characteristic of the chromatic homology. In
other terms, we can say that the chromatic homology is a categorification of
the chromatic polynomial. This holds, of course, for a specific choice of the
(commutative) algebra $A$ (e.g. it must be graded or filtered, and its graded
dimension should be the chromatic polynomial of a vertex). The first question
is: are there natural choices of the algebra $A$ such that the appropriate
Euler characteristic of $C_{\mu}^{*}({\tt G};A)$ is a known invariant of the
graph ${\tt G}$? In general, what are the combinatorial properties of the
graded Euler characteristic of the multipath cohomology of a graph with
coefficients in a graded algebra?

######  Question 8.4 (Relationship with Turner-Wagner theory).

We showed that the chromatic homology and the multipath cohomology, when both
are defined (i.e. $A$ commutative), fit into a long exact sequence. Does it
exist a long exact sequence, or a spectral sequence, featuring both the
multipath and Turner-Wagner homologies with general coefficients?

######  Question 8.5 (Spectral sequences and applications).

A very interesting and deep feature of Khovanov homology is that it admits a
spectral sequence which abuts to a very simple homology called Lee homology
[Lee05]. From this and similar spectral sequences one can extract numerical
invariants with interesting applications to low-dimensional topology and knot
theory. More importantly, these spectral sequences provide structural
information on Khovanov homology. Chromatic homology mimics Khovanov homology.
Hence, it is not surprising to find similar spectral sequences and invariants
in the context of chromatic homology [Zhu21]. Are there similar spectral
sequences for multipath cohomology? If yes, which kind of information can be
extracted from them?

######  Question 8.6 (Persistent multipath cohomology).

Persistent Homology [ELZ02, ZC05] is nowadays one of the main tools adopted in
Topological Data Analysis, with applications in several domains. One usually
starts with a fixed number of data points, joined by (weighted) edges
representing the connections between them. These edges are typically added
gradually; that is, we have a filtration of the resulting (unoriented) graph
${\tt G}$. This filtration is a sequence ${\tt G}_{0}\subset\dots\subset{\tt
G}_{n}$ of spanning sub-graphs of ${\tt G}$. Then, one uses the functorial
properties of the classical homology to obtain information in the form of
persistent homology groups. Within this framework, one usually works with
unoriented graphs, but in concrete applications graphs are often directed; it
is also interesting to compare the undirected versus the directed information
(cf. [CPH21]). Multipath cohomology is a cohomology theory of directed graphs
and it is functorial with respect to morphisms of digraphs with same number of
vertices. It is hence natural to define a persistent multipath cohomology for
filtrations of digraphs. Which information of the input data can multipath
cohomology capture? How does it compare with the analysis using unoriented
graphs?

## References

  * [ABM05] R. Aharoni, E. Berger, and R. Meshulam.  Eigenvalues and homology of flag complexes and vector representations of graphs.  GAFA, Geom. funct. anal., 15:555–566, 2005.
  * [Bjo84] A. Bjorner.  Posets, regular CW complexes and Bruhat order.  European Journal of Combinatorics, 5(1):7–16, 1984.
  * [CCC22] Luigi Caputi, Daniele Celoria, and Carlo Collari.  Monotone cohomologies and oriented matchings, 2022.
  * [CCDT21] L. Caputi, C. Collari, and S. Di Trani.  Combinatorial and topological aspects of path posets, and multipath cohomology, 2021.  Arxiv:2110.11206.
  * [Cha19] A. Chandler.  Thin posets, CW posets, and categorification, 2019.  ArXiv:1911.05600.
  * [CPH21] L. Caputi, A. Pidnebesna, and J. Hlinka.  Promises and pitfalls of topological data analysis for brain connectivity analysis.  NeuroImage, 238:118245, 2021.
  * [CR22] L. Caputi and H. Riihimäki.  Hochschild homology, and a persistent approach via connectivity digraphs.  arXiv e-prints, page arXiv:2204.00462, April 2022.
  * [CYY01] B. Chen, S.-T. Yau, and Y.-N. Yeh.  Graph homotopy and Graham homotopy.  Discrete Mathematics, 241(1):153–170, 2001.  Selected Papers in honor of Helge Tverberg.
  * [ELZ02] H. Edelsbrunner, D. Letscher, and A. Zomorodian.  Topological persistence and simplification.  Discrete Comput. Geom., 28:511–533, 2002.
  * [ET09] B. Everitt and P. Turner.  Homology of coloured posets: A generalisation of Khovanov’s cube construction.  Journal of Algebra, 322(2):429–448, 2009.
  * [ET15] B. Everitt and P. Turner.  Cellular cohomology of posets with local coefficients.  J. Algebra, 439:134–158, 2015.
  * [GLMY20] A. A. Grigor’yan, Yong Lin, Y. V. Muranov, and S.-T. Yau.  Path complexes and their homologies.  Journal of Mathematical Sciences, 248:564–599, 2020.
  * [GLS21] D. Govc, R. Levi, and J. P. Smith.  Complexes of tournaments, directionality filtrations and persistent homology.  Journal of Applied and Computational Topology, 5:313–317, 2021\.
  * [GZ67] P. Gabriel and M. Zisman.  Calculus of Fractions and Homotopy Theory, volume 35.  Springer-Verlag Berlin Heidelberg, 1967.
  * [Hap89] D. Happel.  Hochschild cohomology of finite-dimensional algebras.  Lecture Notes in Math, 1404:108–126, 1989.
  * [Hat00] A. Hatcher.  Algebraic topology.  Cambridge Univ. Press, Cambridge, 2000.
  * [HGR05] L. Helme-Guizon and Y. Rong.  A categorification for the chromatic polynomial.  Algebraic & Geometric Topology, 5(4):1365 – 1388, 2005.
  * [Iva94] A. V. Ivashchenko.  Contractible transformations do not change the homology groups of graphs.  Discrete Mathematics, 126(1):159–170, 1994.
  * [Jon08] J. Jonsson.  Simplicial complexes of graphs, volume 1928 of Lecture Notes in Mathematics.  Springer-Verlag, Berlin, 2008.
  * [Kho00] M. Khovanov.  A categorification of the Jones polynomial.  Duke Math. J., 101(3):359–426, 2000.
  * [Koz08] D. N. Kozlov.  Combinatorial algebraic topology, volume 21 of Algorithms and computation in mathematics.  Springer, Berlin
  * [Lan02] S. Lang.  Algebra., volume 211.  New York, NY: Springer, 2002.
  * [Lee05] E. S. Lee.  An endomorphism of the Khovanov invariant.  Adv. Math., 197(2):554–586, 2005.
  * [Lod98] J.-L. Loday.  Cyclic Homology, volume 301 of Grundlehren der mathematischen Wissenschaften.  Springer Berlin Heidelberg, 1998.
  * [Lur09] J. Lurie.  Higher Topos Theory (AM-170).  Princeton University Press, 2009.
  * [Mac71] S. MacLane.  Categories for the Working Mathematician.  Springer-Verlag, New York, 1971.  Graduate Texts in Mathematics, Vol. 5.
  * [NS18] T. Nikolaus and P. Scholze.  On topological cyclic homology.  Acta Mathematica, 221(2):203 – 409, 2018.
  * [Prz10] J. H. Przytycki.  When the theories meet: Khovanov homology as Hochschild homology of links.  Quantum Topol., 1(2):93–109, 2010.
  * [Put14] K. K. Putyra.  A 2-category of chronological cobordisms and odd Khovanov homology.  Banach Center Publications, 103:291–355, 2014.
  * [Qui73] D. Quillen.  Higher algebraic K-theory: I.  In H. Bass, editor, Higher K-Theories, pages 85–147, Berlin, Heidelberg, 1973. Springer Berlin Heidelberg.
  * [Qui78] Daniel Quillen.  Homotopy properties of the poset of nontrivial $p$-subgroups of a group.  Adv. in Math., 28(2):101–128, 1978.
  * [Roo61] J.-E. Roos.  Sur les foncteurs derives de projlim. Applications.  C. R. Acad. Sci. Paris 252 1961 3702–3704., 252:3702–3704, 1961\.
  * [TW12] P. Turner and E. Wagner.  The homology of digraphs as a generalisation of Hochschild homology.  Journal of Algebra and Its Applications, 11(02):1250031, 2012.
  * [Wac03] M. L. Wachs.  Topology of matching, chessboard, and general bounded degree graph complexes.  volume 49, pages 345–385. 2003.  Dedicated to the memory of Gian-Carlo Rota.
  * [Wes05] D. B. West.  Introduction to graph theory.  New Delhi: Prentice-Hall of India, 2005.
  * [ZC05] A. Zomorodian and G. Carlsson.  Computing persistent homology.  Discrete Comput. Geom., 33:249–274, 2005.
  * [Zhu21] Z. Zhuang.  On the homology theory for the chromatic polynomials, 2021.  ArXiv:2107.03671.

##  Appendix A Proof of Lemma 4.5

######  Lemma A.1.

The function $\sigma_{\rm e}$ in Equation (3) gives a sign assignment on
$P({\tt G})$.

###### Proof.

Consider a square ${\tt H}\prec{\tt H}^{\prime}_{1},{\tt
H}^{\prime}_{2}\prec{\tt H}^{\prime\prime}$ in $P({\tt G})$. Then, there exist
two edges $e_{1}$ and $e_{2}$ of ${\tt G}$ such that ${\tt
H}^{\prime}_{1}={\tt H}\cup e_{1}$, ${\tt H}^{\prime}_{2}={\tt H}\cup e_{2}$,
and ${\tt H}^{\prime\prime}={\tt H}^{\prime}_{2}\cup e_{1}={\tt
H}^{\prime}_{1}\cup e_{2}$ (cf. Example 2.14 and Figure 15).

${\tt H}$${\tt H}^{\prime}_{1}={\tt H}\cup e_{1}$${\tt H}^{\prime}_{2}={\tt
H}\cup e_{2}$${\tt H}^{\prime\prime}={\tt H}^{\prime}_{2}\cup
e_{1}$$\phantom{{\tt H}^{\prime\prime}}={\tt H}^{\prime}_{1}\cup e_{2}$ Figure
15. A square in $P({\tt G})$: four multipaths such that ${\tt H}\prec{\tt
H}^{\prime}_{1},{\tt H}^{\prime}_{2}\prec{\tt H}^{\prime\prime}$.

The proof is split in cases, according to the number of components of ${\tt
H}$ which are merged by adding the edges $e_{1}$ and $e_{2}$. First, adding
both $e_{1}$ and $e_{2}$ to ${\tt H}$ decreases the number of connected
components by at most two. Second, the result of the addition of $e_{1}$ and
$e_{2}$ must still be a multipath – submultipath of ${\tt H}^{\prime\prime}$
to be precise. In particular, observe that cycles are not allowed. It follows
that there are two cases:

  1. (A)

three connected components of ${\tt H}$ merge into a single connected
component of ${\tt H}^{\prime\prime}$;

  2. (B)

four connected components of ${\tt H}$ merge into two connected components of
${\tt H}^{\prime\prime}$;

All cases are divided into subcases depending on the indices of the components
involved (to be more precise, on the relative order of said indices), and on
the orientations of the edges $e_{1}$ and $e_{2}$ – see Figures 16 and 17. We
now proceed with the core of the proof.

  1. (A)

Three connected components, $c_{i}$, $c_{j}$, and $c_{k}$, of the multipath
${\tt H}$ are merged into a single component of ${\tt H}^{\prime\prime}$.
Without loss of generality, up to a permutation of the labels of the
components, we may assume that $i<j<k$. Note that $e_{1}$ and $e_{2}$ cannot
be incident to the same pair of components otherwise ${\tt H}^{\prime\prime}$
would contain a loop. We have six subcases in total – cf. Figure 16. Since the
result of merging the components $c_{i}$, $c_{j}$, and $c_{k}$ must be a
unique simple path, the orientations of $e_{1}$ and $e_{2}$ must be coherent;
that is, the source of an edge has to be the target of the previous one in the
resulting path, and the edges $e_{1}$ and $e_{2}$ can not have same sources or
targets – e.g. if the source of $e_{1}$ lies in $c_{k}$, then the source of
$e_{2}$ cannot lie in $c_{k}$. We report in Table 2 the result of the
computation of the signs of $\sigma_{\rm e}$ in this case.

$c_{i}$$c_{j}$$c_{k}$$e_{1}$$e_{2}$(a)$c_{i}$$c_{j}$$c_{k}$$e_{1}$$e_{2}$(a’)$c_{i}$$c_{j}$$c_{k}$$e_{1}$$e_{2}$(b)$c_{i}$$c_{j}$$c_{k}$$e_{1}$$e_{2}$(b’)$c_{i}$$c_{j}$$c_{k}$$e_{1}$$e_{2}$(c)$c_{i}$$c_{j}$$c_{k}$$e_{1}$$e_{2}$(c’) Figure 16. A schematic description of the subcases of Case A. Note that, since the merge of the components $c_{i}$, $c_{j}$, and $c_{k}$ must be a path, all possible orientations of $e_{1}$ and $e_{2}$ are precisely those illustrated. subcase | $\sigma_{\rm e}({\tt H},{\tt H}^{\prime}_{1})$ | $\sigma_{\rm e}({\tt H}^{\prime}_{1},{\tt H}^{\prime\prime})$ | $\sigma_{\rm e}({\tt H},{\tt H}^{\prime}_{2})$ | $\sigma_{\rm e}({\tt H}^{\prime}_{2},{\tt H}^{\prime\prime})$
---|---|---|---|---
(a) | $j+1$ | $k$ | $k+1$ | $j+1$
(a’) | $j$ | $k-1$ | $k$ | $j$
(b) | $k+1$ | $j$ | $k$ | $j$
(b’) | $k$ | $j+1$ | $k+1$ | $j+1$
(c) | $j+1$ | $k-1$ | $k$ | $j+1$
(c’) | $j$ | $k$ | $k+1$ | $j$
Table 2. Computations for all subcases of case (A)

  2. (B)

Four connected components of ${\tt H}$, say $c_{i}$, $c_{j}$, $c_{k}$ and
$c_{h}$, are pairwise merged to obtain exactly two connected components of
${\tt H}^{\prime\prime}$. Without loss of generality we may assume $i<j<k<h$.
We have twelve relevant cases, but we can reduce them to six; in fact, a
change in the orientation of the edges induces a change of the parity of the
index. As a consequence, a simultaneous change in the orientations of both
$e_{1}$ and $e_{2}$ affect our computation by a global sign. All six cases are
shown in Figure 17 and the results are summarised in Table 3.

$c_{i}$$c_{j}$$c_{h}$$c_{k}$$e_{1}$$e_{2}$(a)$c_{i}$$c_{j}$$c_{h}$$c_{k}$$e_{1}$$e_{2}$(b)$c_{i}$$c_{j}$$c_{h}$$c_{k}$$e_{1}$$e_{2}$(c)$c_{i}$$c_{j}$$c_{h}$$c_{k}$$e_{1}$$e_{2}$(d)$c_{i}$$c_{j}$$c_{h}$$c_{k}$$e_{1}$$e_{2}$(e)$c_{i}$$c_{j}$$c_{h}$$c_{k}$$e_{1}$$e_{2}$(f) Figure 17. A schematic description of the subcases of Case (B) up to a global change in the orientations of $e_{1}$ and $e_{2}$. subcase | $\sigma_{\rm e}({\tt H},{\tt H}^{\prime}_{1})$ | $\sigma_{\rm e}({\tt H}^{\prime}_{1},{\tt H}^{\prime\prime})$ | $\sigma_{\rm e}({\tt H},{\tt H}^{\prime}_{2})$ | $\sigma_{\rm e}({\tt H}^{\prime}_{2},{\tt H}^{\prime\prime})$
---|---|---|---|---
(a) | $j+1$ | $k$ | $k+1$ | $j+1$
(b) | $j+1$ | $k-1$ | $k$ | $j+1$
(c) | $k+1$ | $h$ | $h+1$ | $k+1$
(d) | $k+1$ | $h-1$ | $h$ | $k+1$
(e) | $h+1$ | $k+1$ | $k+1$ | $h$
(f) | $h+1$ | $k$ | $k$ | $h$
Table 3. Computations for all relevant subcases of case (B)

It follows from (A) and (B) that $\sigma_{\rm e}$ is a sign assignment on
$P({\tt G})$, which concludes the proof. ∎