Biplab Basak^a , Vanny Doem^b , Chandal Nahak^b

^aDepartment of Mathematics, Indian Institute of Technology Delhi, Delhi, India

biplab@iitd.ac.in, vanny.doem@gmail.com, cnahak@maths.iitkgp.ac.in

This paper presents three main results concerning the coloring of discrete d-pseudomanifolds: (1) the general chromatic bounds d + 1 ≤ X(K) ≤ 2d + 2 for any d-pseudomanifold K; (2) an improved bound X(K) ≤ 2d + 1 for a d-pseudomanifold expressible as a join K = S ^k + K′ , where S k is a cyclic k-sphere and K′ is a subpseudomanifold; (3) the optimal bound X(K) ≤ ⌈3(d + 1)/2⌉, where ⌈−⌉ is a ceiling function, under the additional assumptions that the spherical join factor S k is an even-cyclic k-sphere and its dimension k is sufficiently close to d.

Keywords: Combinatorial pseudomanifolds, geometric coloring, chromatic graph theory Mathematics Subject Classification: 05C15, 05C10, 57M15

DOI: 10.5614/ejgta.2026.14.1.8

1. Introduction

The chromatic theory of geometric graphs has its profound modern origin in the combinatorial topology pioneered by Steve Fisk in a seminal series of works [2, 3, 4, 5]. Fisk investigated the coloring of triangulated manifolds and demonstrated how purely combinatorial arguments could solve geometric problems. However his framework was inherently tied to classical simplicial complexes and their topological realizations.

The translation of this paradigm into a pure language of finite graph theory was achieved by Oliver Knill through his theory of discrete manifolds [9]. By defining a discrete d-manifold M purely as a finite simple graph where every unit sphere, the subgraph generated by the neighbors

Received: 17 August 2023, Revised: 18 December 2025, Accepted: 10 January 2026.

^bDepartment of Mathematics, Indian Institute of Technology Kharagpur, Kharagpur, India

of x, is a (d − 1)-sphere, Knill provided foundational bounds for the chromatic number X(M) of any discrete d-manifold M, [9, Theorem 1],

\[d+1 \le X(M) \le 2d+2. \tag{1}\]

Furthermore using the Zykov join for two general finite graphs G and H (Definition 2.3), where the chromatic number X(G + H) = X(G) + X(H) is additive [9, §3.1], Knill constructed highdimensional spheres with chromatic number scaling as 3k or 3k + 1 in [9, §3.2]. This leads to the conjecture that the optimal bounds might be tighter, as discussed in [9, §1]

\[d+1 \le X(M) \le 2d+1 \tag{2}\]

and

\[d+1 \le X(M) \le \lceil 3(d+1)/2 \rceil \tag{3}\]

where ⌈−⌉ is a ceiling function. Therefore Knill's work can be viewed as a direct graph-theoretic reformulation and extension of the geometric coloring problems initiated by Fisk in [5].

This present article extends the chromatic theory from discrete d-manifolds to a significantly broader class of discrete d-pseudomanifolds (Definition 3.1). The first central question is whether the foundational bounds in (1) persist for this more general class. We affirm that the chromatic number of any discrete d-pseudomanifold K satisfies the same robust bounds in (1) (Theorem 3.1).

Theorem A. The chromatic number X(K) of any d-pseudomanifold K satisfies

\[d+1 \le X(K) \le 2d+2.\]

We construct a family of k-spheres S ^k by taking Zykov joins of multiple cyclic graphs Cⁿ for n ≥ 4. The number of component cycles depends on the parity of k, and we classify these spheres as "even-cyclic" or "odd-cyclic" based on whether the cyclic graphs Cn, n ≥ 4, have even or odd length (Definition 3.2). From this we then consider a discrete d-pseudomanifold K that can be decomposed as K = S ^k + K′ . We thus obtain the tighter bounds in (2) (Theorem 5.1).

Theorem B. If K = S ^k+K′ where S k is a cyclic k-sphere and K′ is a (d−k−1)-pseudomanifold,

\[d+1 \le X(K) \le 2d+1.\]

Additionally we demonstrate that under optimal conditions on the spherical factor S k , say S k is an even-cyclic k-sphere (Definition 3.2), and S k is of sufficiently high dimension (condition (8)), the conjectured optimal ceiling in (3) is attainable (Theorem 5.2).

Theorem C. If K = S ^k + K′ where S k is an even-cyclic k-sphere, K′ is a (d − k − 1) pseudomanifold, and k is sufficiently close to d,

\[d+1 \le X(K) \le \lceil 3(d+1)/2 \rceil\]

where ⌈−⌉ is a ceiling function.

1.1. Organization

In §2 we recall some preliminaries that are used throughout the paper. In §3 we deal with the chromatic number of a general d-pseudomanifold, proving Theorem A, and in §4 we deal with the foundational results for proving Theorems B and C in §5.

1.2. Notation

Throughout this paper we use the following notations.

• G and H denote finite graphs.
• X(−) is the chromatic number of a graph, and L(−) is the unit link of a vertex, the subgraph generated by its neighbors.
• K stands for a discrete pseudomanifold, and M for a discrete manifold. For convenience we sometimes omit the prefix 'discrete'.

2. Preliminaries

2.1. Duality in Graphs

Let G = (V, E) be a graph with vertices V and edges E. We recall two types of duality in graph-theoretic notions as follows.

Definition 2.1. Let H be a subgraph of a finite simple graph G. Define a complementary dual graph Hˆ in G to be the intersection of all unit links of vertices in H, written as,

\[\hat{H} = \bigcap_{y \in H} L(y).\]

For example, the complementary dual graph of the empty graph ∅ in G is G itself (and vice versa); the complementary dual graph of a one-point subgraph x in G is the unit link L(x) in G; and the complementary dual graph of a complete graph Kⁿ in K^m is the Km−n, formed by the complementary vertices of Kn.

Definition 2.2. A dual graph G^∗ = (V ∗ , E^∗ ) of a d-graph G = (V, E) is defined to have the maximal d-simplices as vertices, and connects two different maximal simplices if they intersect in a (d − 1)-simplex.

For example, the dual graph of Wn, a wheel graph with a cyclic graph Cⁿ as its boundary, is Cn; the dual graph of the octahedron graph (2-sphere) is the cube graph; and the dual graph of the 3-sphere is the tesseract. Notice that in this paper the term 'sphere' refers a topological discrete sphere in the theory of discrete manifolds [9, §1.1], [6, §8].

2.2. Arithmetic on Graphs

In this subsection we recall two algebraic operations on graphs: The Zykov join first introduced by Zykov in [10], and the Cartesian simplex product by Stanley-Reisner [7].

Definition 2.3. Let G = (V, E) and H = (W, F) be finite simple graphs. Define the Zykov join G + H to be the disjoint union G ∪ H where every vertex in G is connected to every vertex in H. Algebraically,

\[G + H = (V \cup W, E \cup F \cup VW)\]

where V W denotes all the edges connecting every vertex in V to every vertex in W.

Definition 2.4. Given two finite simple graphs G and H, the Cartesian simplex product (G × H)¹ is the graph whose vertices are all ordered pairs (g, h), where g and h are complete subgraphs of G and H, and where two distinct vertices (g, h),(u, v) are adjacent if either g ≤ u, h ≤ v, or u ≤ g, v ≤ h. In symbols,

\[(G \times H)_1 = (c(G) \times c(H), \{(a, b) \mid a \le b \text{ or } b \le a\})\]

where c(−) denotes the set of complete subgraphs.

If H = 1 is the one-point graph, the product (G × 1)¹ is the Barycentric refinement of G.

3. Chromatic Number of Pseudomanifolds

There is a geometric construction of topological discrete spheres, which leads to a new formulation of a discrete d-manifold in terms of graph-theoretic notions as in [9, §1.1], [6, §8]. In this section we define another new class of d-graphs, which we call "discrete d-pseudomanifolds". For conventional purpose we sometimes omit the prefix 'discrete'.

Definition 3.1. A discrete d-pseudomanifold is a finite simple graph K where every unit link L(x), the subgraph generated by the neighbors of x, is a discrete (d − 1)-pseudomanifold. It is based on the presumption that the empty graph ∅ is a (−1)-pseudomanifold, and a 1-pseudomanifold is a cyclic graph Cⁿ for n ≥ 4.

In Definition 3.1 one notices that every unit link L(x) is essentially a pseudomanifold, which is not necessarily a topological sphere; one can call this unit link a "pseudosphere". Therefore a pseudomanifold is, in general, not a topological manifold anymore.

With Definition 2.3 and for every n ≥ 4, Cⁿ is a 1-pseudomanifold in Definition 3.1, we define:

Definition 3.2. A k-dimensional cyclic sphere S k is a k-sphere constructed as the Zykov join

\[S^{k} = \begin{cases} \underbrace{C_{n} + C_{n} + \dots + C_{n}}_{\lceil (k+1)/2 \rceil \text{ copies}}, & k \text{ is odd,} \\ \underbrace{C_{n} + \dots + C_{n}}_{(\lceil (k+1)/2 \rceil - 1) \text{ copies}}, & k \text{ is even.} \end{cases}\]

where the 0-sphere S ⁰ = {{a, b}, ∅} represents two isolated vertices and ⌈−⌉ is a ceiling function. If the integer n ≥ 4 is even (odd), then S k is called an even-cyclic (odd-cyclic) k-sphere.

Definition 3.3. A subpseudomanifold K' of a d-pseudomanifold K is also a pseudomanifold whose vertex and edge sets are subsets of the vertex and edge sets of the d-pseudomanifold.

Using Definitions 2.1 and 3.1, we generate the following facts.

Proposition 3.1. For a complete subgraph \(K_n \leq K\), the complementary dual \(\hat{K}_n\) is a (d-n)-pseudomanifold.

Proof. We proceed by induction on n. From the induction step

\[\hat{K}_{n-1} = \bigcap_{y \in K_{n-1}} L(y)\]

is a (d-n+1)-pseudomanifold. Now we prove for n. Write \(K_n=\{v_1,v_2,\cdots,v_n\}\). Fix \(v=v_n\) and write \(K_n=K_{n-1}+v\). Following Definition 2.1 we have

\[\hat{K}_n = \bigcap_{y \in K_{n-1}} L(y) \cap L(v) = \hat{K}_{n-1} \cap L(v).\]

Then we must verify that \(v \in \hat{K}_{n-1}\). For every \(y \in K_{n-1}\) and \(v \neq y\), we have v is adjacent to y since \(K_n\) is a complete graph. Hence for every \(y \in K_{n-1}\) we obtain \(v \in L(y) \leq \hat{K}_{n-1}\).

Consider \(L_{\hat{K}_{n-1}}(v)\), the unit link of v within \(\hat{K}_{n-1}\). As \(\hat{K}_{n-1}\) is an induced subgraph of \(K_n\),

\[L_{\hat{K}_{n-1}}(v) = \{u \in \hat{K}_{n-1} \mid u \text{ adjacent to } v \in K_n\} = \hat{K}_{n-1} \cap L(v) = \hat{K}_{n-1}.\]

Since \(\hat{K}_{n-1}\) is a (d-n+1)-pseudomanifold by the induction hypothesis, the unit link of every vertex within \(\hat{K}_{n-1}\) is a ((d-n+1)-1)=(d-n)-pseudomanifold. This shows that \(\hat{K}_n\) is a (d-n)-pseudomanifold, which proves the statement.

Proposition 3.2. For any subgraph \(H \leq K\), the complementary dual \(\hat{H}\) is either the empty graph, a subgraudomanifold, a complete graph, a pyramid, or the entire pseudomanifold K.

Proof. Let H be a subgraph of K. Fix \(v \in H\) and write H = H' + v. We then inductively assume that the statement holds for a lower cardinality of vertices |V(H)|. From this we have

\[\hat{H} = \hat{H}' \cap L(v),\]

and \(\hat{H}'\) can be one of the following possible cases.

Case 1. \(\hat{H}' = \emptyset\) or \(\hat{H}' = K\). If \(\hat{H}' = \emptyset\), then \(\hat{H} = \emptyset\). If \(\hat{H}' = K\), then \(\hat{H} = L(v)\) is merely a (d-1)-pseudomanifold by Definition 3.1.

Case 2. \(\hat{H}' = K'\) is a subpseudomanifold. Hence \(\hat{H} = K' \cap L(v)\). As K' and L(v) are subpseudomanifolds, \(K' \cap L(v)\) is an induced subgraph of both. By the structure of pseudomanifolds, \(K' \cap L(v)\) is either the empty graph, a subpseudomanifold, a complete subgraph (if the intersection is a complete subgraph), or a pyramid (if the intersection is a cone over a subpseudomanifold).

Case 3. \(\hat{H}' = K_n\) is a complete graph. Thus \(\hat{H} = K_n \cap L(v)\). Since every induced subgraph of a complete graph \(K_n\) is complete, the \(\hat{H}\) is either \(\emptyset\) or a complete subgraph.

Case 4. \(\hat{H}'\) is a pyramid P = K' + w such that K' is a subpseudomanifold. Then

\[\hat{H} = (K' + w) \cap L(v).\]

If v=w, then \(\hat{H}=K'\cap L(v)\) reduces to Case 2. Moreover if \(v\neq w\) and v is adjacent to w, then \(w\in L(v)\) and \(\hat{H}\) may retain the pyramid structure or become a complete graph. If \(v\neq w\) and v is not adjacent to w, then \(w\notin L(v)\) and \(\hat{H}=K'\cap L(v)\) is again falling into Case 2.

With all these cases, the proof is complete.

We now produce necessary elements, on the duality of a d-pseudomanifold K, for proving the chromatic number X(K) in Theorem 3.1. First we notice that the dual \(K^*\) of a d-pseudomanifold K is (d+1)-regular since every simplex in K is connected with exactly d+1 neighbors.

Proposition 3.3. For every d-pseudomanifold K, the dual graph \(K^*\) is triangle-free.

Proof. Suppose \(K^*\) contains a triangle formed by three maximal d-simplices \(\sigma_1, \sigma_2, \sigma_3\), where each pair \(\sigma_i \cap \sigma_j = \tau_{ij}\) shares a (d-1)-simplex. These (d-1)-simplices are distinct as every (d-1)-simplex in K is contained in exactly two maximal d-simplices, due to the (d+1)-regularity of \(K^*\).

Consider \(\sigma = \sigma_1 \cap \sigma_2 \cap \sigma_3\). As \(\tau_{12}, \tau_{13}\) are distinct (d-1)-faces of \(\sigma_1\), the intersection \(\sigma\) is a (d-2)-simplex. From Definition 3.1 we have \(L(\sigma)\), the unit link of the (d-2)-simplex in K, is a 1-pseudomanifold \(C_n, n \geq 4\). However, \(\sigma_1, \sigma_2, \sigma_3\) yield three distinct vertices, namely, \(a, b, c \notin \sigma\) such that

\[\sigma_1 = \sigma \cup \{a, b\}, \sigma_2 = \sigma \cup \{a, c\}, \sigma_3 = \sigma \cup \{b, c\}.\]

In \(L(\sigma)\) the vertices a,b,c are pairwise adjacent since \(\sigma \cup \{a,b\}, \sigma \cup \{a,c\}, \sigma \cup \{b,c\}\) are d-simplices. Hence \(L(\sigma)\) contains a triangle formed by vertices a,b,c, contradicting the fact that \(L(\sigma)\) is \(C_n, n \geq 4\). Therefore we conclude that \(K^*\) cannot contain a triangle.

Proposition 3.4. For every d-pseudomanifold K, the dual graph \(K^*\) can be cut into trees.

Proof. Following Proposition 3.3 we can break each cycle \(C_n\), \(n \ge 4\), into a spanning tree of its vertices as follows. For a connected K, the \(K^*\) is connected. Choose any spanning tree T of \(K^*\), and then remove every edge of \(K^*\) that is not in T; this results in a single tree T. Furthermore if K is disconnected, the \(K^*\) is disconnected. Hence applying the same terminology to each component yields a spanning forest, which is a family of trees, one for each component.

Now we are ready to prove our main result. We demonstrate its proof on the lower bound by observing the existence of the maximal simplices in the d-pseudomanifold K, and on the upper bound by decomposing the dual graph \(K^*\).

Theorem 3.1. The chromatic number X(K) of any d-pseudomanifold K satisfies

\[d+1 \le X(K) \le 2d+2.\]

Proof. Let K be a connected d-pseudomanifold. The lower bound is clear by definition. We now proceed to the upper bound by using the structure of K^∗ as follows. First notice that K^∗ is connected, all vertices in K^∗ correspond to the maximal d-simplices (facets) in K, and two distinct vertices in K^∗ are adjacent if their corresponding facets in K share a (d − 1)-simplex in K.

• Step 1. Decomposing K^∗ . By Proposition 3.4 we can cut K^∗ into a spanning forest F by removing edges from cycles until no cycles remain. Let F1, F² be two disjoint vertex sets of a bipartition of the spanning forest F. Observe that every edge in F connects a vertex in F¹ to a vertex in F2, and F¹ ∪ F² contains all vertices corresponding to all facets in K.
• Step 2. Coloring via F1, F2. Consider a tree T within F1, where vertices and edges in T respectively correspond to the facets and the connected facets in K. Coloring all vertices in T respectively corresponds to coloring all vertices of all facets in K by using the first batch of d + 1 colors

\[C_1 = \{1, 2, \cdots, d+1\},\\]

and ensuring that the coloring is proper, meaning that the adjacent vertices in K get different colors. Similarly coloring all vertices of a tree T ′ within F² respectively corresponds to coloring all vertices of all facets in K by the second different batch of d + 1 colors

\[C_2 = \{d+2, d+3, \cdots, 2d+2\}.\]

We repeat this process for every tree in F¹ and F2.

Step 3. Combining F¹ ∪ F² and C¹ ∪ C2. By applying the coloring procedure in Step 2, every vertex of K is assigned exactly one color from C¹ ∪ C2. More precisely if a vertex in F corresponding to a facet in K first appears in F1, it receives a color from C¹ while processing F1; if it appears in F2, or remains uncolored after F¹ is processed, it receives a color from C² while processing F2. Since C¹ and C² are disjoint, no vertex is ever assigned two different colors. Thus the procedure yields a well-defined coloring of K by using the color set

\[C_1 \cup C_2 = \{1, 2, \cdots, d+1, d+2, \cdots, 2d+1, 2d+2\}.\]

We now verify that the coloring is proper. Indeed, let u, v be adjacent vertices in K. Then u, v must lie in a common maximal simplex σ ∈ K. As the vertex set of K^∗ is partitioned into F¹ and F2, either σ corresponds to a vertex in F¹ or F2. If σ corresponds to a vertex in F1, during the processing of F¹ in Step 2, the vertices of σ were assigned distinct colors from C1, so u, v have different colors. The same holds if σ corresponds to a vertex in F2. Hence there are no two adjacent vertices that share a color. Therefore we obtain X(K) ≤ C¹ ∪ C² = 2d + 2.

Corollary 3.1. If K′ ≤ K is a subpseudomanifold of K, then X(K′ ) ≤ X(K). In particular,

\[\dim K' + 1 \le X(K') \le 2\dim K' + 2.\]

Proof. Immediately follows from Theorem 3.1.

Remark 3.1. In the technical sense of Theorem 3.1, one inspects that K^∗ can always be cut into a spanning forest F by removing edges from cycles until no cycles, as shown in [9, Theorem 1].

One may also see that the discrete d-manifolds M and the d-pseudomanifolds K share the same general chromatic bounds

\[d+1 \le X(M), X(K) \le 2d+2.\]

As discussed in [9, §1], for the discrete d-manifolds M, there is evidence supporting a conjectured tighter upper bound ⌈3(d + 1)/2⌉ where ⌈−⌉ is a ceiling function, and constructions exist that reach chromatic numbers as high as ⌈3d/2⌉. Whether a more flexible local structure of the discrete d-pseudomanifolds K permits chromatic numbers exceeding this conjectured upper bound for dmanifolds, or whether it imposes even stricter limits, is a subject for further investigation in §5.

4. Chromatic Arithmetic on Pseudomanifolds

In this section we examine two graph operations and their chromatic properties on the pseudomanifolds. The chromatic number is additive for general graphs [9, §3]. However an interesting point here is that the Zykov join introduced in Definition 2.3 and the Cartesian simplex product in Definition 2.4 preserve the structure of pseudomanifolds, graphs that recursively have the property that all unit links are again one lower-dimensional pseudomanifolds.

Proposition 4.1. Let K be an m-pseudomanifold and K′ an n-pseudomanifold. Then the Zykov join K + K′ is an (m + n + 1)-pseudomanifold.

Proof. We prove this proposition by induction on the total dimension m + n. We inductively assume that the statement holds for all the Zykov joins where the total sum of the dimensions ≤ m + n. We then prove for K with dimension m and K′ with dimension n, and the total sum of dimension is m + n + 1.

Suppose v is a vertex in K + K′ . Then there are two possibilities, whether v originates from K or K′ , say,

\[L_{K+K'}(v) = L_K(v) + K'\] respectively \(L_{K+K'}(v) = K + L_{K'}(v)\).

By Definition 3.1, LK(v) and LK′(v) are (m − 1)-pseudomanifold and (n − 1)-pseudomanifold, respectively. From the induction hypothesis the join of an (m − 1)-pseudomanifold LK(v) and an n-pseudomanifold K′ , and that of an m-pseudomanifold K and an (n − 1)-pseudomanifold LK′(v) , both are (m + n)-pseudomanifolds. By observing that every unit link in K + K′ is an (m + n)-pseudomanifold, the K + K′ is an (m + n + 1)-pseudomanifold.

Notice that for two general graphs G and H, there is a formula [1, Lemma 2]

\[\dim(G+H) = \dim G + \dim H + 1.\]

Furthermore by [9, Lemma 1], the chromatic number X(G + H) is additive:

\[X(G+H) = X(G) + X(H). (4)\]

A conjecture on sphere coloring was stated in [8, §8.3]: Every k-sphere S ^k has X(S k ) = k + 1 or X(S k ) = k + 2. It was disproved by [9, Corollary 1]: There are S ²k−¹ with X(S 2k−1 ) = 3k and S ^2k with X(S 2k ) = 3k + 1. This shows that the chromatic number of spheres can be relatively large. In contrast we present even-cyclic spheres with relatively small chromatic numbers.

Proposition 4.2. There are even-cyclic spheres with chromatic numbers

\[X(S^{2k-1}) = 2k\] and \(X(S^{2k}) = 2k + 1\).

Proof. Follow Definition 3.2 and observe that S ^2k = S ²k−¹ + S 0 .

To be used later, we record the chromatic numbers of S ^k with respect to Definition 3.2 as

\[X(S^k) = k + 1\], and \(X(S^k) = \begin{cases} (3k+2)/2, & k \text{ is even} \\ (3k+3)/2, & k \text{ is odd} \end{cases}\) (5)

where the first is from an even-cyclic k-sphere, and the second from an odd-cyclic k-sphere. Using Definition 2.4 we also record the following result.

Proposition 4.3. Let K be an m-pseudomanifold and K′ an n-pseudomanifold, with m, n ≥ 1. Then the Cartesian simplex product (K × K′ )¹ is an (m + n)-pseudomanifold.

Proof. The result follows directly from Definition 2.4 by induction on the total dimension m + n, using the recursive property of pseudomanifolds in Definition 3.1.

Recall the construction in [9, §5]. Let x = (x0, . . . , xd−2) be a (d − 2)-simplex in a dpseudomanifold K. A "dual link of the simplex x" is defined to be the 1-link

\[L(x_0) \cap \cdots \cap L(x_{d-2}).\]

It is denoted by O(K) the 'Fisk set' in the odd structure as in [5, VI.2]. By inspection we have:

Proposition 4.4. For an m-pseudomanifold K and an n-pseudomanifold K′ with m, n ≥ 2,

\[O(K + K') = K + O(K') \cup O(K) + K'.\]

Proof. This follows by the same argument as in the proof of [9, Lemma 6].

5. The Limit of Chromatic Pseudomanifolds

The purpose of this section is to examine the sharpness of the bound 2d + 2 in Theorem 3.1. For the sharper bounds we follow the conjectures in [9, §1] and interpret them in the context of pseudomanifolds. The first version of the conjectures is more practical, while the second is stricter.

Conjecture 1. For any d-pseudomanifold K, the chromatic number X(K) satisfies

\[d+1 \le X(K) \le 2d+1.\]

Conjecture 2. For any d-pseudomanifold K, the chromatic number X(K) satisfies

\[d+1 \le X(K) \le \lceil 3(d+1)/2 \rceil\]

where ⌈−⌉ is a ceiling function.

Responding to Conjectures 1 and 2, we record the following special tests.

Theorem 5.1. If a d-pseudomanifold K = S ^k + K′ such that S k is a cyclic k-sphere in (5) and K′ is a (d − k − 1)-pseudomanifold,

\[d+1 \le X(K) \le 2d+1.\]

Proof. Rewriting the identity (4)

\[X(K) = X(S^k) + X(K'). (6)\]

To obtain an upper bound, we use the maximum possible chromatic numbers

\[X(K') \le 2(d-k) \text{ and } X(S^k) = \begin{cases} (3k+2)/2, & k \text{ is even,} \\ (3k+3)/2, & k \text{ is odd.} \end{cases}\] (7)

where the first factor is by Theorem 3.1 and the second by (5). We consider two cases.

Case 1. k is even (k = 2p). Then using expressions (6) and (7) we obtain

\[X(K) = X(S^{2p}) + X(K') \le 2d + 1 - p\]

which implies X(K) ≤ 2d + 1 for p ≥ 0.

Case 2. k is odd (k = 2p − 1). Again applying (6) and (7),

\[X(K) = X(S^{2p-1}) + X(K') \le 2d + 2 - p\]

from which it follows that X(K) ≤ 2d + 1 for p ≥ 1. This completes the proof.

The equation (5) shows that the chromatic number of cyclic spheres depends on its type: It is relatively small for even-cyclic spheres, and relatively large for odd-cyclic spheres. Hence with this information in mind we deduce the following analyses.

Analysis A: S k is an even-cyclic k-sphere. By Theorem 3.1 and presentations (5) and (6)

\[X(K) = X(S^k) + X(K') \le 2d - k + 1.\]

The desired bound X(K) ≤ ⌈3(d + 1)/2⌉ holds if and only if k ≥ 2d + 1 − ⌈3(d + 1)/2⌉ which is equivalent to saying that the dimension k is sufficiently close to d, more specifically,

\[k \ge \begin{cases} d/2 - 1, & d \text{ is even,} \\ (d+1)/2 - 1, & d \text{ is odd.} \end{cases}\] (8)

Analysis B: S k is an odd-cyclic k-sphere. In this case the upper bound X(K) ≤ ⌈3(d + 1)/2⌉ may no longer hold as shown in Table 1. In the computation of Table 1, to obtain a worst-case upper bound, we take the maximum possible chromatic number X(K′ )max = 2(d − k) for dim K′ ≥ 2, ensuring the subsequent inequalities hold in general.

We formulate the above Analyses A and B in the following statement.

Theorem 5.2. If a d-pseudomanifold K = S ^k + K′ such that S k is an even-cyclic k-sphere in (5), K′ is a (d − k − 1)-pseudomanifold, and k satisfies condition (8),

\[d+1 \le X(K) \le \lceil 3(d+1)/2 \rceil\]

where ⌈−⌉ is a ceiling function.

Coloring discrete pseudomanifolds | B. Basak, et al.

Table 1. Write X(K)max = X(S k ) + X(K′ )max, X(K′ )max = 2(d − k), and X(K)bound = ⌈3(d + 1)/2⌉.

Acknowledgment

We sincerely thank the referees for their insightful feedback, which greatly improved this paper. The first author acknowledges support from SERB MATRICS Grant No. MTR/2022/000036, and the second author from ICCR Grant No. PHN/ICCR/321/1/2021, India.

References

• [1] K. Betre and E. Salinger. The inductive graph dimension from the minimum edge clique cover. Graphs Combin., 37(6):2637–2654, 2021.
• [2] S. Fisk. Combinatorial structure on triangulations. I. The structure of four colorings. Advances in Math., 11:326–338, 1973.
• [3] S. Fisk. Combinatorial structures on triangulations. II. Local colorings. Advances in Math., 11:339–350, 1973.
• [4] S. Fisk. Combinatorial structures on triangulations. III. Coloring with regular polyhedra. Advances in Math., 12:296–305, 1974.
• [5] S. Fisk. Variations on coloring, surfaces and higher-dimensional manifolds. Advances in Math., 25(3):226–266, 1977.
• [6] O. Knill. Coloring graphs using topology. arXiv preprint arXiv:1412.6985, 2014.
• [7] O. Knill. On the arithmetic of graphs. arXiv preprint arXiv:1706.05767, 2017.
• [8] O. Knill. Eulerian edge refinements, geodesics, billiards and sphere coloring. arXiv preprint arXiv:1808.07207, 2018.
• [9] O. Knill. Coloring discrete manifolds. arXiv preprint arXiv:2106.14374, 2021.
• [10] A.A. Zykov. On some properties of linear complexes. Mat. Sb. (N.S.), 24/66:163–188, 1949.