Open Access 12062020  Original Paper
Colouring simplicial complexes via the Lechuga–Murillo’s model
Published in: Applicable Algebra in Engineering, Communication and Computing  Issue 2/2022
Abstract
Lechuga and Murillo showed that a nonoriented, simple, connected, finite graph G is kcolourable if and only if a certain pure Sullivan algebra associated to G and k is not elliptic. In this paper, we extend this result to simplicial complexes by means of several notions of colourings of these objects.
1 Introduction
Graph Theory and Rational Homotopy Theory were first related by Lechuga and Murillo in a celebrated paper [15] (see also [16]) where they show that a nonoriented, simple, connected, finite graph can be kcoloured, \(k\ge 2\), if and only if a certain Sullivan algebra associated to the graph is not elliptic. They also provide a link between Rational Homotopy Theory and algorithmic complexity by proving that the problem of graph colourability can be reduced in polynomial time to the problem of determining the ellipticity of a certain Sullivan algebra. Hence, since the former is an NPcomplete problem, the latter is an NPhard problem.
This interplay between Graph Theory and Rational Homotopy Theory has been proven fruitful: recently, Costoya and Viruel were able to use this interaction to solve a question of realisability of groups [4, 5], and applications of these results to further problems were subsequently found [2, 3].
Advertisement
The aim of this work is to extend the result of Lechuga and Murillo from graphs to (finite) simplicial complexes by considering eleven notions of colourability for these objects, many of which can be found in the literature. We refer to these colourings as \({\mathfrak {C}}_i\)colouring, for \(i=1,2, \ldots , 11\) (see Definitions 2.1, 2.4, 2.6, and 3.3), and prove the following two results:
Theorem 1.1
For any \(k\ge 2\), any \(i=1,2,\ldots ,11\), and any connected simplicial complex X, which is assumed to be strongly connected and homogeneous for \(i = 8,9,10,11\), there exists a pure Sullivan algebra \({{\mathcal {M}}}^i_k (X)\) which is not elliptic if and only if X is \({\mathfrak {C}}_i\)kcolourable.
Theorem 1.2
For \(i\in \{1,7,8,9,10,11\}\) and \(k\ge 3\), or for \(i\in \{4,5,6\}\) and \(k\ge 4\), determining if a connected simplicial complex is \({\mathfrak {C}}_i\)kcolourable is an NPhard problem.
Advertisement
As for the necessary background, we assume that the reader is familiar with basics of algorithmic complexity and Rational Homotopy Theory, for which [12] and [9] are, respectively, excellent references. In particular, concerning algorithmic complexity we will use that the problems of totalkcolourability, \(k\ge 4\), edgekcolourability, \(k\ge 3\), and kcolourability, \(k\ge 3\), are NPcomplete [13, 17, 18].
Regarding Rational Homotopy Theory, we just recall that a (simply connected) Sullivan algebra, denoted \((\Lambda W,d)\), is a commutative differential graded algebra, which is free as an algebra generated by the (simply connected) graded rational vector space W, and where the differential d is decomposable. A Sullivan algebra is elliptic if both W and \(H^*(\Lambda W,d)\) are finite dimensional, and pure if \(d W^{\mathrm{even}}=0\) and \(d W^{\mathrm{odd}}\subset \Lambda W^{\mathrm{even}}\).
We now recall the fundamental construction in [15] associated to any \(k\ge 2\) and any nonoriented, simple, connected, finite graph \(G = (V,E)\), where V and E respectively denote the sets of vertices and edges of G. Consider the pure Sullivan algebra \(S_k(G) =(\Lambda W_{G,k},d)\) whereFor this construction, the following holds:
$$\begin{aligned} W_{G,k}^{\mathrm{even}}&= \langle x_v \mid v\in V \rangle , \quad x_v=2, \quad d(x_v)=0, \\ W_{G,k}^{\mathrm{odd}}&= \langle y_{(u, v)} \mid (u, v)\in E\rangle , \quad y_{(u, v)} = 2k3, \quad d(y_{(u, v)}) = \Sigma _{l=1}^k x_u^{kl}x_v^{l1}. \end{aligned}$$
Theorem 1.3
([15, Theorem 3]) The graph G is kcolourable if and only if the Sullivan algebra \(S_k(G)\) is not elliptic.
To relate this result with algorithmic complexity it is convenient to keep in mind that a graph \(G = (V,E)\) is usually encoded by its adjacency matrix \(A=(a_{ij})_{i,j\in V}\) in which \(a_{ij}=1\) if \((i, j)\in E\) and \(a_{ij}=0\) otherwise. In binary, the codification of this matrix has length \(\log _2 n+n^2\), where n is the number of vertices of G.
Throughout this paper, every considered simplicial complex X is assumed to be finite. The dimension of a simplex \(\sigma \in X\), denoted \(\dim \sigma\), is its cardinality minus one. The dimension of X, denoted \(\dim X\), is the dimension of any of its largest simplices. Given \(s\ge 0\), we denote the set of simplices of X of dimension s by \(X^s\). In particular, \(X^0\) is the set of vertices of X, which is often denoted by V. The sskeleton of X is the subsimplicial complex of X spanned by \(X^s\), and we denote it by \(X^{(s)}\). Note that \(X^{(1)}\) is trivially identified to a nonoriented, simple graph, and we say that X is connected if \(X^{(1)}\) is a connected graph.
2 Models for colourings of connected simplicial complexes
In the spirit of Theorem 1.3, we will associate to finite, connected simplicial complexes precise pure Sullivan algebras whose ellipticity encode different notions of colouring of simplicial complexes.
2.1 Colourings arising from hypergraphs
Recall that a hypergraph is a pair \(H = (V,E)\) formed by a nonempty set of vertices V and a set of hyperedges E, each of them being a nonempty subset of V. Two vertices are adjacent if they belong to a common hyperedge. An hyperedge e is incident to a vertex v if \(v\in e\). Two hyperedges e and \(e'\) are adjacent if \(e\cap e'\ne \emptyset\). The hypergraph H is connected if given any two vertices \(u,v\in V\) there is a sequence of hyperedges \(e_1,e_2,\dots ,e_n\) such that \(u\in e_1\), \(v\in e_n\) and \(e_i\) is adjacent to \(e_{i+1}\), for \(i=1,2,\dots ,n1\).
A vertex kcolouring of a hypergraph \(H = (V,E)\), see [1, §3.1], is a map \(\varphi :V\rightarrow \{1,2,\dots ,k\}\) such that for any hyperedge e of more than one vertex \(\varphi (e) > 1\). Namely, at least two vertices of e have different colours. Moreover, if for any \(e\in E\) and any two different vertices \(u, v\in e\) we have that \(\varphi (u)\ne \varphi (v)\), we say that \(\varphi\) is a strong vertex kcolouring.
On the other hand, [1, §3.2.5] a hyperedge colouring for H is a map \(\varphi :E\rightarrow \{1,2,\dots ,k\}\) such that \(\varphi (e)\ne \varphi (e')\) for any pair of different but adjoint hyperedges e and \(e'\).
Finally, [7], a total colouring of H is a map \(\varphi :V\cup E \rightarrow \{1,2,\dots ,k\}\) such that any pair formed by either two adjacent vertices, two adjacent hyperedges or an hyperedge and any of its incident vertices have different images through \(\varphi\).
Trivially, a simplicial complex X can be regarded as a hypergraph \(H = (V,E)\) where \(V = X^0\) and \(E = X\). Hence, the above notions of colourability automatically translate to the following definition. Note that a vertex kcolouring of a simplicial complex is always a strong vertex kcolouring.
Definition 2.1
Let X be a simplicial complex.
(1)
A vertex kcolouring of X (\({\mathfrak {C}}_1\)kcolouring) is a map \(\varphi :V\rightarrow \{1,2,\dots ,k\}\) such that if \(\sigma \in X\) and \(u,v\in \sigma\), \(u\ne v\), then \(\varphi (u)\ne \varphi (v)\).
(2)
A face kcolouring of X (\({\mathfrak {C}}_2\)kcolouring) is a map \(\varphi :X\rightarrow \{1,2,\dots ,k\}\) such that \(\varphi (\sigma )\ne \varphi (\tau )\) whenever \(\sigma \ne \tau\), \(\sigma \cap \tau \ne \emptyset\).
(3)
A total kcolouring of X (\({\mathfrak {C}}_3\)kcolouring) is a map \(\varphi :X\rightarrow \{1,2,\dots ,k\}\) such that \(\varphi (u)\ne \varphi (v)\) for any \(u,v\in V\) with \(\{u,v\}\in X\), and \(\varphi (\sigma )\ne \varphi (\tau )\) for any pair of different simplices \(\sigma ,\tau\) with nonempty intersection.
Note that a total kcolouring yields both a vertex kcolouring and a face kcolouring. We prove:
Proposition 2.2
For any simplicial complex X and any \(i =1,2,3\), there is a pure Sullivan algebra \({\mathcal {M}}_k^i(X)\) which is not elliptic if and only if X is \({\mathfrak {C}}_i\)kcolourable.
Proof
Associated to X consider \(G_1 = X^{(1)}\) the graph given by its 1skeleton. On the other hand, let \(G_2\) be the graph whose vertex set is the set of simplices of X and whose edges are pairs of distinct simplices with a common face. Finally, let \(G_3\) be the graph whose vertex set is again the set of simplices of X and whose edges are also pairs of distinct simplices with nonempty intersection, together with pairs of vertices giving raise to a 1simplex. Observe that \(G_1\), \(G_2\) and \(G_3\) are respectively the 2section graph, intersection graph and total graph of the hypergraph given by X (see [1, 7]).
It is then clear from Definition 2.1 that a \({\mathfrak {C}}_i\)kcolouring of X is precisely a kcolouring of \(G_i\), \(i = 1,2,3\). Furthermore, the graphs \(G_1\), \(G_2\) and \(G_3\) are connected as a consequence of X being connected. To finish, define \({\mathcal {M}}_k^i(X) = S_k(G_i)\) and apply Theorem 1.3. \(\square\)
2.2 Colourings of simplicial complexes
The colourings in §2.1 are originally defined for hypergraphs, thus they do not take consideration of the additional structure of simplicial complexes. For that reason, we introduce the following:
Definition 2.3
Let X be a simplicial complex. We denote the respective chromatic numbers by \(\chi _r(X)\) and \(\chi '_r(X)\).
(1)
An ascending kcolouring of X in dim r is a map \(\varphi :X^r \rightarrow \{1,2,\dots ,k\}\) such that if \(\sigma ,\tau \in X^r\), \(\sigma \cup \tau \in X^{r+1}\), then \(\varphi (\sigma )\ne \varphi (\tau )\).
(2)
A descending kcolouring of X in dim r is a map \(\varphi :X^r \rightarrow \{1,2,\dots ,k\}\) such that if \(\sigma ,\tau \in X^r\), \(\sigma \cap \tau \in X^{r1}\), then \(\varphi (\sigma )\ne \varphi (\tau )\).
An ascending kcolouring of X in dim r is a colouring of the graphwhereas a descending kcolouring of X in dim r is a colouring ofcalled the rth exchange graph of X (see [10]). However, Theorem 1.3 cannot be used to model the colourings in Definition 2.1 using these graphs, as they may not be connected. We treat this issue in Sect. 3.
$$\begin{aligned} G_r(X)=\big (X^r,\{(\sigma ,\tau )\mid \sigma \cup \tau \in X^{r+1}\}\big ), \end{aligned}$$
(1)
$$\begin{aligned} G'_r(X)=\big (X^r,\{(\sigma ,\tau )\mid \sigma \cap \tau \in X^{r1}\}\big ), \end{aligned}$$
(2)
Instead, in this section we use the ascending and descending colourings to introduce new colourings which we can model in the spirit of Proposition 2.2.
Definition 2.4
Let X be a simplicial complex.
(1)
A complete ascending kcolouring of X (\({\mathfrak {C}}_4\)kcolouring) is a map \(\varphi :X\rightarrow \{1,2,\dots ,k\}\) such that, for any \(r,s\in \{0,1,\dots ,\dim X\}\), if \(\sigma ,\tau \in X^r\), \(\sigma \cup \tau \in X^{r+1}\), or if \(\sigma \in X^r\), \(\tau \in X^s\), \(r\ne s\), then \(\varphi (\sigma )\ne \varphi (\tau )\).
(2)
A complete descending kcolouring of X (\({\mathfrak {C}}_5\)kcolouring) is a map \(\varphi :X\rightarrow \{1,2,\dots ,k\}\) such that, for any \(r,s\in \{0,1,\dots ,\dim X\}\), if \(\sigma ,\tau \in X^r, \sigma \cap \tau \in X^{r1}\), or if \(\sigma \in X^r, \tau \in X^s, r\ne s\), then \(\varphi (\sigma )\ne \varphi (\tau )\).
(3)
A map \(\varphi :X \rightarrow \{1,2,\dots ,k\}\) is a full kcolouring of X (\({\mathfrak {C}}_6\)kcolouring) if for \(\sigma ,\tau \in X\) such that \(\sigma \subset \tau\), or \(\sigma ,\tau \in X^0\), \(\sigma \cup \tau \in X^1\), or for \(1\le r\le \dim X\), \(\sigma ,\tau \in X^r\), \(\sigma \cap \tau \in X^{r1}\), we have that \(\varphi (\sigma )\ne \varphi (\tau )\).
Let \(G_1 = (V_1, E_1)\) and \(G_2 = (V_2, G_2)\) be two graphs. Recall that the sum of \(G_1\) and \(G_2\) is a graph \(G = G_1+G_2\) with vertex set \(V_1\sqcup V_2\) and edges \(E_1\cup E_2\cup \{(u,v)\mid u\in V_1, v\in V_2\}\). The sum of any two graphs is connected. Also recall that the union of \(G_1\) and \(G_2\) is the graph \(G_1\cup G_2\) with vertex set \(V_1\cup V_2\) and edges \(E_1\cup E_2\).
Proposition 2.5
For any simplicial complex X and any \(i=4,5,6\), there is a pure Sullivan algebra \({\mathcal {M}}_k^i(X)\) which is not elliptic if and only if X is \({\mathfrak {C}}_i\)kcolourable.
Proof
First, note that a complete ascending (resp. descending) kcolouring of X is an ascending (resp. descending) kcolouring of X in dim r when restricted to \(X^r\). Furthermore, simplices of different dimensions receive different colours. It becomes clear that if we defineX admits a complete ascending (resp. descending) kcolouring if and only if the connected graph \(G_4\) (resp. \(G_5\)) is kcolourable.
$$\begin{aligned} G_4&= G_0(X) + G_1(X) + \dots + G_{\dim X}(X), \\ G_5&= G'_0(X) + G'_1(X) + \dots + G'_{\dim X}(X), \end{aligned}$$
Regarding the full kcolouring, let I denote the strict inclusion graph of X, that is, a graph with vertex set X and where \((\sigma ,\tau )\) is an edge if and only if either \(\sigma \subset \tau\) or \(\tau \subset \sigma\). Define a graphThen \(G_6\) is connected since I is so. Furthermore, X is fullkcolourable if and only if \(G_6\) is kcolourable. To finish, define \({\mathcal {M}}_k^i(X) = S_k(G_i)\), \(i=4,5,6\), and apply Theorem 1.3. \(\square\)
$$\begin{aligned}G_6 = I \cup \big (G_0(X)\sqcup G_1'(X)\sqcup \dots \sqcup G'_{\dim X}(X)\big ).\end{aligned}$$
We model one last colouring in this section. In [8] the authors introduce the following, more relaxed definition of vertex colouring:
Definition 2.6
Let \(k, s \ge 1\) and let X be a simplicial complex. A (k, s)colouring of X (\({\mathfrak {C}}_7\)(k, s)colouring) is a map \(f: V \rightarrow \{1,2,\dots ,k\}\) such that, for every \(\sigma \in X\) and for all \(1\le t \le k\), \( \sigma \cap f^{1}(t)  \le s\). Let \({\text {chr}}^s(X)\) denote the least integer k such that X is (k, s)colourable.
A Sullivan algebra whose ellipticity codifies the (k, s)colourability of a simplicial complex had already been obtained in [6]. However, we can use the work in [14] to provide a different construction of one such algebra:
Proposition 2.7
For any simplicial complex X there exists a pure Sullivan algebra \({\mathcal {M}}_{k,s}^7(X)\) which is not elliptic if and only if X is \({\mathfrak {C}}_7\)(k, s)colourable.
Proof
In [14, Theorem 2] the authors show thatwhere \(\mathrm {BCP}^s(X)\) is a set of partitions of the vertex set of X and \(G_0(P)\) is a 1dimensional simplicial complex associated to one such partition P, see [14, Definition 3]. It quickly follows that when regarding \(G_0(P)\) as a graph, \({\text {chr}}^1 \big (G_0(P)\big )=\chi \big (G_0(P)\big )\). Furthermore, \(G_0(P)\) is connected for every \(P\in \text {BCP}^s(X)\). DefineLet us show that \({\mathcal {M}}_{k,s}^{7}(X)\) is the desired algebra.
$$\begin{aligned} {\text {chr}}^s (X) = \min _{P \in \mathrm {BCP}^s(X)} {\text {chr}}^1 \big (G_0(P)\big ), \end{aligned}$$
$$\begin{aligned}{\mathcal {M}}_{k,s}^7(X) = \bigotimes _{P \in \mathrm {BCP}^s(X)} S_k\big (G_0(P)\big ).\end{aligned}$$
Recall that the tensor product of Sullivan algebras is not elliptic if and only if at least one of the factors is not elliptic. Therefore, if \({\mathcal {M}}_{k,s}^7(X)\) is not elliptic, there exists \(P\in \mathrm {BCP}^s(X)\) such that \(S_k\big (G_0(P)\big )\) is not elliptic. Then by Theorem 1.3\(G_0(P)\) is kcolourable, so \(\chi \big (G_0(P)\big )={\text {chr}}^1\big (G_0(P)\big )\le k\), thus X is (k, s)colourable. Reciprocally, if \({\mathcal {M}}_{k,s}^7(X)\) is elliptic, then \(S_k\big (G_0(P)\big )\) is elliptic for every \(P\in \text {BCP}^s(X)\). Therefore, \(G_0(P)\) is not kcolourable, meaning that \(\chi \big (G_0(P)\big )={\text {chr}}^1\big (G_0(P)\big ) > k\), for every \(P\in \text {BCP}^s\). Therefore, X is not (k, s)colourable. \(\square\)
3 Models for colourings of strongly connected homogeneous simplicial complexes
As mentioned in Sect. 2.2, the colourings in Definition 2.3 cannot be immediately modelled since the graphs that encode them, \(G_r(X)\) [see (1)] and and \(G_r'(X)\) [see (2)], are not necessarily connected. In this section we further restrict the class of simplicial complexes that we are considering as to be able to model these colourings.
Recall that a simplicial complex X of dimension \(\dim X = n\) is strongly connected if for any two ndimensional simplices \(\sigma\), \(\tau\) there exist \(\{\sigma _0 = \sigma , \sigma _1,\dots ,\sigma _k = \tau \}\subset X^n\) such that \(\sigma _{i1}\cap \sigma _i\in X^{n1}\), for \(i = 1,2,\dots ,k\). Equivalently, X is strongly connected if and only if \(G'_{\dim (X)}\) is connected. On the other hand, X is homogeneous if every vertex is contained in an ndimensional simplex. Then, if X is homogeneous and strongly connected, so is \(X^{(k)}\), for \(0\le k \le n\). Therefore:
Proposition 3.1
For any ndimensional strongly connected homogeneous simplicial complex X, \(G_r(X)\) and \(G'_s(X)\) are connected, for \(0\le r < n\) and \(0 < s \le n\).
Proof
The connectivity of \(G'_s(X)\), for \(0< s \le n\) is an immediate consequence of the strong connectivity of \(X^{(s)}\). Let us prove the connectivity of \(G_r(X)\), \(0\le r < n\). Take \(\sigma ,\tau \in X^r\). Since X is homogeneous, we can find \({\bar{\sigma }},{\bar{\tau }}\in X^{r+1}\) such that \(\sigma \subset {\bar{\sigma }}\) and \(\tau \subset {\bar{\tau }}\). Then, since \(X^{(r+1)}\) is strongly connected, we can find \(\{{\bar{\sigma }}_0 = {\bar{\sigma }}, {\bar{\sigma }}_1,\dots ,{\bar{\sigma }}_k = {\bar{\tau }}\}\subset X^{r+1}\) such that \(\sigma _i = {\bar{\sigma }}_{i1}\cap {\bar{\sigma }}_{i}\in X^r\), \(i = 1,2,\dots ,k\). It is now immediate to check that \(\sigma \sigma _1 \dots \sigma _{k} \tau\) is a path in \(G_r(X)\) joining \(\sigma\) and \(\tau\). \(\square\)
An immediate application of Theorem 1.3 yields the following result:
Proposition 3.2
For any ndimensional strongly connected homogeneous simplicial complex X and for \(0\le r <n\) (resp. for \(0<s\le n\)), there exists a Sullivan algebra \({\mathcal {M}}_k (X,r)\) (resp. \({\mathcal {M}}'_k(X,s)\)) which is not elliptic if and only if X admits an ascending kcolouring in dim r (resp. a descending kcolouring in dim s).
We now introduce the last collection of colourings.
Definition 3.3
We say that a map \(\varphi :X\rightarrow \{1,2,\dots ,k\}\) is:The respective chromatic numbers are denoted \(\chi _{\max }(X)\), \(\chi '_{\max }(X)\), \(\chi _{\min }(X)\) and \(\chi '_{\min }(X)\).

a maximal ascending kcolouring (\({\mathfrak {C}}_8\)kcolouring) if for every \(0\le r \le \dim X\) the restriction \(\varphi _{X^r}\) is an ascending kcolouring in dim r for X.

a maximal descending kcolouring (\({\mathfrak {C}}_{9}\)kcolouring) if for every \(0\le s \le \dim X\) the restriction \(\varphi _{X^s}\) is a descending kcolouring in dim s for X.

a minimal ascending kcolouring (\({\mathfrak {C}}_{10}\)kcolouring) if there exists \(0\le r < \dim X\) such that \(\varphi _{X^r}\) is an ascending kcolouring in dim r for X.

a minimal descending kcolouring (\({\mathfrak {C}}_{11}\)kcolouring) if there exists \(0 < s \le \dim X\) such that \(\varphi _{X^s}\) is a descending kcolouring in dim s for X.
Let \(G_1 = (V_1, E_1)\) and \(G_2 = (V_2, G_2)\) be two graphs. The cartesian product \(G_1\square G_2\) is a graph with vertex set \(V_1\times V_2\) and edge set \(\big\{\big ((u_1,u_2),(v_1,v_2)\big )\mid {u_1 = v_1 \text { and } (u_2,v_2)\in E_2 \text { or } (u_1,v_1)\in E_1 \text { and } u_2 = v_2}\big\}\). Note that \(\chi (G_1\square G_2)=\max \big \{\chi (G_1),\chi (G_2)\big \}\) (see [11, Theorem 26.1]). Furthermore, the cartesian product of connected graphs is connected ([11, Corollary 5.3]). Then:
Proposition 3.4
For any simplicial complex X and any \(i = 8,9,10,11\), there is a pure Sullivan algebra \({\mathcal {M}}_k^i(X)\) which is not elliptic if and only if X is \({\mathfrak {C}}_i\)kcolourable.
Proof
Note that any map \(X^{\dim (X)}\rightarrow \{1,2,\dots ,k\}\) (resp. \(X^0\rightarrow \{1,2,\ldots ,k\}\)) is an ascending colouring in dimension \(\dim (X)\) (resp. a descending colouring in dimension 0). Then, \(\chi _{\dim (X)}(X) = \chi '_0(X)=1\). It follows immediately from Definition 3.3 that \(\chi _{\max }(X) = \max _{0 \le r < \dim X} \{\chi _r(X)\}\) and that \(\chi '_{\max }(X) = \max _{0 < s\le \dim X}\{\chi '_s(X)\}\). Consider the graphsThen, since \(\chi \big (G_r(X)\big ) = \chi _r(X)\) and \(\chi \big (G'_s(X)\big ) =\chi '_s(X)\), we deduce that \(\chi (G_8) = \chi _{\max }(X)\) and \(\chi (G_9) = \chi '_{\max }(X)\), so X admits a maximal ascending (resp. descending) kcolouring if an only if \(G_8\) (resp. \(G_9\)) is kcolourable. Furthermore, both \(G_8\) and \(G_9\) are connected as a consequence of Proposition 3.1. Therefore, for \(i = 8,9\) it suffices to define \({\mathcal {M}}_k^i(X) = S_k(G_i)\) and apply Theorem 1.3.
$$\begin{aligned} G_8 = G_0(X)\square G_1(X)\square \cdots \square G_{n1}(X), \ G_9 = G'_1(X)\square G'_2(X)\square \cdots \square G'_n(X). \end{aligned}$$
We now consider the minimal colourings. It follows from Definition 3.3 that \(\chi _{\min }(X) = \min _{0\le r < \dim X}\{\chi _r(X)\}\) and that \(\chi '_{\min }(X) = \min _{0 < s \le \dim X}\{\chi '_r(X)\}\). By a reasoning analogous to that of Proposition 2.7, the desired algebras areThe result follows. \(\square\)
$$\begin{aligned} {\mathcal {M}}_k^{10}(X)= & {} S_k\big (G_0(X)\big ) \otimes S_k\big (G_1(X)\big )\otimes \dots \otimes S_k\big (G_{n1}(X)\big ),\\ {\mathcal {M}}_k^{11}(X)= & {} S_k\big (G'_1(X)\big ) \otimes S_k\big (G'_2(X)\big )\otimes \dots \otimes S_k\big (G'_{n}(X)\big ). \end{aligned}$$
4 Algorithmic complexity of simplicial complex colourings
If G is a graph, it can be regarded as a simplicial complex X(G) whose 0simplices and 1simplices are, respectively, the vertices and edges of G. Such a simplicial complex can be encoded using an adjacency matrix, so its codification has the same length as that of G.
In this section we show that the (edge, total) colourability of a graph G is equivalent to the \({\mathfrak {C}}_i\)colourability of X(G) for certain indices i. As a consequence, we immediately deduce Theorem 1.2.
Remark 4.1
It is immediate that the kcolourability of a graph G is equivalent both to the \({\mathfrak {C}}_1\)kcolourability and the \({\mathfrak {C}}_7\)(k, 1)colourability of X(G). Similarly, the total kcolourability of G is equivalent to the \({\mathfrak {C}}_6\)kcolourability of X(G).
Proposition 4.2
The kcolourability of a graph G is equivalent both to the \({\mathfrak {C}}_4\)\((k+1)\)colourability and the \({\mathfrak {C}}_i\)kcolourability, \(i = 8,10\), of \(X = X(G)\).
Proof
We begin with the \({\mathfrak {C}}_4\)colourability. Let \(\psi :V\rightarrow \{1,2,\dots ,k\}\) be a kcolouring of G. Then, the map \(\varphi :X\rightarrow \{1,2,\ldots ,k+1\}\) defined byis a \({\mathfrak {C}}_4\)\((k+1)\)colouring of X. Reciprocally, if \(\varphi :X\rightarrow \{1,2,\dots ,k+1\}\) is a \({\mathfrak {C}}_4\)\((k+1)\)colouring of X, we may assume that at least one 1simplex receives image \(k+1\), so \(k+1\not \in \varphi (X^0)\). The map \(\psi :X^0 = V\rightarrow \{1,2,\dots ,k\}\) taking v to \(\psi (v) = \varphi (\{v\})\) is a kcolouring of G.
$$\begin{aligned} \varphi (\sigma ) = {\left\{ \begin{array}{ll} \psi (\sigma ), &{} \text {if } \sigma \in X^0, \\ k+1, &{} \text {if } \sigma \in X^1. \end{array}\right. } \end{aligned}$$
We now consider the \({\mathfrak {C}}_i\)kcolourability, \(i = 8,10\). First, if \(\psi :V \rightarrow \{1,2,\dots ,k\}\) is a kcolouring of G, X admits a \({\mathfrak {C}}_i\)kcolouring defined byReciprocally, if \(\varphi :X\rightarrow \{1,2,\dots ,k\}\) is a \({\mathfrak {C}}_i\)kcolouring of X, \(i = 8,10\), the restriction \(\psi =\varphi _{X^0} :X^0= V \rightarrow \{1,2,\dots ,k\}\) is a kcolouring of G. \(\square\)
$$\begin{aligned} \varphi (\sigma ) = {\left\{ \begin{array}{ll} \psi (\sigma ), &{} \text {if } \sigma \in X^0, \\ k, &{} \text {if } \sigma \in X^1. \end{array}\right. } \end{aligned}$$
Proposition 4.3
The edge kcolourability of a graph G is equivalent both to the \({\mathfrak {C}}_5\)\((k+1)\)colourability and the \({\mathfrak {C}}_i\)kcolourability, \(i=9,11\), of \(X=X(G)\).
Proof
We begin with the \({\mathfrak {C}}_5\)\((k+1)\)colourability. If \(\psi :E\rightarrow \{1,2,\ldots ,k\}\) is an edge kcolouring of G, the map \(\varphi :X(G) = X\rightarrow \{1,2,\dots ,k+1\}\) defined byis a \({\mathfrak {C}}_5\)\((k+1)\)colouring of X. Reciprocally, if \(\varphi :X\rightarrow \{1,2,\ldots ,k+1\}\) is a \({\mathfrak {C}}_5\)\((k+1)\)colouring of X, we may suppose that at least one 0simplex receives image \(k+1\), thus \(k+1\not \in \varphi (X^1)\). Then, the map \(\psi = \varphi _{X^1}:X^1 = E\rightarrow \{1,2,\dots ,k\}\) is an edge kcolouring of G.
$$\begin{aligned} \varphi (\sigma )={\left\{ \begin{array}{ll} \psi (\sigma ), &{} \text {if } \sigma \in X^1, \\ k+1, &{} \text {if } \sigma \in X^0. \end{array}\right. } \end{aligned}$$
We continue with the \({\mathfrak {C}}_i\)kcolourability, \(i=9,11\). If \(\psi :E\rightarrow \{1,2,\dots ,k\}\) is an edge kcolouring of G, X admits a \({\mathfrak {C}}_i\)kcolouring \(\varphi :X\rightarrow \{1,2,\dots ,k\}\) defined byReciprocally, if \(\varphi :X\rightarrow \{1,2,\dots ,k\}\) is a \({\mathfrak {C}}_i\)kcolouring of X, \(i = 9,11\), the restriction \(\psi =\varphi _{X^1} :X^1= E \rightarrow \{1,2,\dots ,k\}\) is an edge kcolouring of G. \(\square\)
$$\begin{aligned} \varphi (\sigma )= {\left\{ \begin{array}{ll} \psi (\sigma ), &{} \text {if } \sigma \in X^1,\\ k, &{} \text {if } \sigma \in X^0. \end{array}\right. } \end{aligned}$$
Acknowledgements
The author is thankful to Carballés, Costoya and Viruel for their insightful comments and guidance. The author is also thankful to the referee, whose comments helped improve the presentation of this work.
Open AccessThis article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.