Open Neighborhood Coloring of Prisms

1 Introduction

All the graphs considered here are undirected, connected and simple. We use the standard terminologies and the terms not defined here may be found in [1-3]. A proper coloring of a graph is an assignment of colors to the vertices such that adjacent vertices receive different colors. The minimum number of colors required for such a coloring is called the chromatic number of the graph denoted by \(\chi(G)\). In other words, a coloring is an assignment of non negative integers to the vertices of G such that adjacent vertices receive different labels.

A L(h,k) labeling [4] is an assignment of non negative integers to the vertices of G such that adjacent vertices are labelled using colors at least h apart, and vertices having a common neighbour are labelled using colors at least k apart. Most of the work in literature deals with the definition of L(h,k) labeling with \(h \ge k\) [5-11]. The L(h,k) labeling problem is studied mainly to avoid hidden

terminal interference in multihop radio networks in [12] and for code assignment in computer networks in [13].

The concept of open neighbourhood coloring was introduced by Geetha. K.N., et al. [14] and is akin to the definition of L(h,k) labeling with h=0 and k=1 [15]. It is defined as a coloring \(f:V\to Z^+\), such that for each \(w\in V\) and \(\forall u,v\in N(w),\ f(u)\neq f(v)\). The maximum value of \(f(w),\ \forall w\in V(G)\) is called the span of the open neighborhood coloring f. The minimum span of f over all the open neighbourhood colorings f is called open neighbourhood chromatic number of G, denoted by \(\chi_{onc}(G)\). The example shown in the Figures 1, 2 and 3 below clearly indicate the difference between proper coloring, L(0,1) labeling and open neighborhood coloring of a graph G.

Figure 1 Proper coloring of a graph G.

Figure 2 L(0,1) labeling of a graph G.

Figure 3 Open neighborhood coloring of a graph G

The open neighborhood chromatic number of certain standard graphs like path, cycle, trees, complete bipartite graph and the triangular lattice, which is an infinite graph has been computed in [14]. In this paper we find the open neighborhood chromatic number of prism graph, a particular case of generalized Petersen graph GP(n,k).

The generalized Petersen graph denoted GP(n,k) where \(n \ge 3\) is a graph with vertex set \(\left\{u_1,u_2,....u_n,v_1,v_2,....,v_n\right\}\) and edge set \(\left\{u_i\,u_{i+1},u_i\,v_i,v_iv_{i+k}:i=1,....,n\right\}\) where subscripts are under modulo n and \(k < \frac{n}{2}\). The vertices \(\left\{u_1,u_2,....u_n\right\}\) are called the inner polygon vertices and the vertices \(\left\{v_1,v_2,....,v_n\right\}\) are called the outer polygon vertices. In particular, if k=1, the generalized Petersen graph becomes GP(n,1) which is isomorphic to the Cartesian product of \(C_n\) with \(P_n\) called as the prism graph as shown in Figure 4.

Figure 4 The prism GP(n,1).

2 Some Preliminary Results

In this section we state some of the preliminary results on open neighborhood coloring from [14].

Theorem 2.1. Let f be open neighborhood coloring of G(V, E) with span \((f) = \chi_{onc}(G)\). If u, v are the end vertices of a path of length 2 in G then \(f(u) \neq f(v)\).

Theorem 2.2. For any graph G(V, E), \(\chi_{onc}(G) \ge \Delta(G)\).

Theorem 2.3. If H is a connected subgraph of G, then \(\chi_{onc}(H) \leq \chi_{onc}(G)\).

Theorem 2.4. The open neighborhood chromatic number of a connected graph G is one if and only if \(G \cong K_1\) or \(K_2\).

3 Open Neighborhood Coloring of Prisms

Observation 3.1. In the prism graph, it is obvious that, the vertices that are connected to any vertex \(u_i\), \(1 \le i \le n\), by a path of length two are \(u_{i\pm 2}, v_{i\pm 1}\) where the suffix is under modulo n. Similarly, the vertices that are connected to any vertex \(v_i\), \(1 \le i \le n\), by a path of length two are \(v_{i\pm 2}, u_{i\pm 1}\) where the suffix is under modulo n.

We now define a \(P_3\) - independent set as follows:

Definition 3.2. A subset S of V(G) such that no two vertices of S are end vertices of a path of a length two in G is called a \(P_3\) - independent set of G.

Lemma 3.3. Let GP(n,1), where \(n \ge 3\) be any prism. For each k, \(0 \le k \le 2\) define the set \(S_k = \{u_i, v_i \mid i \equiv k \pmod{3}\}\). Then each set \(S_k\), is a \(P_3\)-independent set if and only if \(n \equiv 0 \pmod{3}\).

Proof. Let \(n \equiv 0 \pmod 3\). Now, \(S_0 = \{u_i, v_i / i \equiv 0 \pmod 3\}\). Also \(i \equiv 0 \pmod 3\) implies \(i+2, i-1 \equiv 2 \pmod 3\) and \(i+1, i-2 \equiv 1 \pmod 3\). Therefore, \(u_{i\pm 2}, v_{i\pm 1}, v_{i\pm 2}, u_{i\pm 1} \notin S_0\). Hence by observation 3.1, \(S_0\) is a \(P_3\)-independent set. Similarly it can be proved that \(S_1\) and \(S_2\) are \(P_3\)-independent sets.

We prove the converse in two cases.

Case (1). Suppose \(n \equiv 1 \pmod{3}\). Then \(u_1, v_1, u_n, v_n \in S_1\). But \(u_n\) and \(v_1\) are end vertices of a path of length two and hence \(S_1\) fails to be a \(P_3\) - independent set, a contradiction.

Case (2). Suppose \(n \equiv 2 \pmod{3}\). Then \(u_2, v_2, u_n, v_n \in S_2\). But \(u_n\) and \(u_2\) are the end vertices of a path of length two and hence \(S_2\) fails to be a \(P_3\)-independent set, a contradiction.

Hence the result

Lemma 3.4. Let \(S \subset GP(n,1)\) be any \(P_3\)-independent set of GP(n,1), where \(n \ge 3\). For each k, \(0 \le k \le 2\), if \(u_i \in S\) where \(i \equiv k \pmod{3}\) then for every \(u_{i,j}, v_{j} \in S\), we must have \(j \equiv k \pmod{3}\).

Proof. We now prove the case of k = 0.

Let \(u_i \in S\), where \(i \equiv 0 \pmod{3}\). Now, as S is a \(P_3\)- independent set, by observation 3.1, \(u_{i\pm 2}, v_{i\pm 1} \notin S\). Also \(i \equiv 0 \pmod{3} \Rightarrow i+2, i-1 \equiv 2 \pmod{3}\) and \(i+1, i-2 \equiv 1 \pmod{3}\). Therefore, \(u_j, v_j \notin S\) if \(j \equiv 1, 2 \pmod{3}\). Hence S contains only vertices of the form \(u_j, v_j\) where \(j \equiv 0 \pmod{3}\).

The cases of k = 1 and k = 2 follow similarly.

Theorem 3.5. For the prism graph GP(n,1), with \(n \ge 3\),

\[\chi_{onc}(G) = \begin{cases} 3, & \text{if } n \equiv 0 \pmod{3}, \\ 4, & \text{otherwise.} \end{cases}\]

Proof. We prove the theorem in three cases.

Case (1). \(n \equiv 0 \pmod{3}\)

By Theorem 2.2, \(\chi_{onc}(G) \ge 3\). We now show that \(\chi_{onc}(G) = 3\). In this case, the vertex set of GP(n,1), can be partitioned into three \(P_3\) - independent sets namely \(S_0, S_1\) and \(S_2\) as defined in Lemma 3.3. A single color can be assigned to all vertices in each of the sets and hence \(\chi_{onc}(G) = 3\) for \(n \equiv 0 \pmod{3}\).

We now show that three colors are not sufficient in the next two cases and hence at least four colors are necessary for an open neighborhood coloring of the prism.

Case (2). \(n \equiv 1 \pmod{3}\).

For each k, \(0 \le k \le 2\), let \(S_k = \{u_i, v_i \mid i \equiv k \pmod{3}\}\) where \(1 \le i \le n-1\) be three \(P_3\)- independent sets of GP(n,1), constructed as mentioned in Lemma 3.4. Then, by Lemma 3.3, for each k, \(0 \le k \le 2\), \(u_n, v_n \notin S\). For each k, \(0 \le k \le 2\), we may assign a single color to all the vertices of \(S_k\). Now

vertices \(u_n\) and \(v_n\) are not assigned any color and hence at least one more color is required.

We now show that four colors are sufficient for an open neighborhood coloring of the prism for \(n \equiv 1 \pmod{3}\).

Define the labeling \(f: V(G) \to Z^+\) as

\[f(v_i) = f(u_i) = \begin{cases} 1, & \text{if } i \equiv 1 \pmod{3}, \\ 2, & \text{if } i \equiv 2 \pmod{3}, \\ 3, & \text{if } i \equiv 0 \pmod{3}, \\ 4, & \text{if } i = n. \end{cases}\]

We first consider the vertices of the inner polygon.

For all i, \(2 \le i \le n-2\), \(N(u_i) = \{u_{i-1}, u_{i+1}, v_i\}\), where the suffix is under modulo n.

If \[i \equiv 1 \pmod{3}\] then \(f(u_{i-1}) = 3\), \(f(u_{i+1}) = 2\) and \(f(v_i) = 1\).
If \(i \equiv 2 \pmod{3}\) then \(f(u_{i-1}) = 1\), \(f(u_{i+1}) = 3\) and \(f(v_i) = 2\).
If \(i \equiv 0 \pmod{3}\) then \(f(u_{i-1}) = 2\), \(f(u_{i+1}) = 1\) and \(f(v_i) = 3\).
Hence for all \(i, 2 \le i \le n-2\), \(f(u_{i-1}) \ne f(u_{i+1}) \ne f(v_i)\).

We now consider the vertices of the outer polygon.

For all i, \(2 \le i \le n-2\), \(N(v_i) = \{v_{i-1}, v_{i+1}, u_i\}\), where the suffix is under modulo n.

If i \equiv 1 \pmod{3} then f(v_{i-1}) = 3, f(v_{i+1}) = 2 and f(u_i) = 1.

If i \equiv 2 \pmod{3} then f(v_{i-1}) = 1, f(v_{i+1}) = 3 and f(u_i) = 2.

If i \equiv 0 \pmod{3} then f(v_{i-1}) = 2, f(v_{i+1}) = 1 and f(u_i) = 3.

Hence for all i, 2 \le i \le n - 2, f(v_{i-1}) \ne f(v_{i+1}) \ne f(u_i).

For i = 1, n, n - 1, we make the following observations:

1. When i=1, \(N(u_1) = \{u_2, u_n, v_1\}\), suffix is under modulo n and from the definition of f, we observe that \(f(u_2) = 2\), \(f(u_n) = 4\), \(f(v_1) = 1\). Thus \(f(u_2) \neq f(u_n) \neq f(v_1)\).

• 2. When i=1, \(N(v_1) = \{v_2, v_n, u_1\}\), suffix is under modulo n and it can be observed that \(f(u_1) = 1\), \(f(v_2) = 2\), \(f(v_n) = 4\). Thus \(f(v_1) \neq f(v_2) \neq f(v_n)\).
• 3. When i=n-1, \(N(u_{n-1}) = \{v_{n-1}, u_n, u_{n-2}\}\), suffix is under modulo n and we have \(f(v_{n-1}) = 3\), \(f(u_n) = 4\), \(f(u_{n-2}) = 2\). Thus \(f(v_{n-1}) \neq f(u_n) \neq f(u_n)\).
• 4. When i=n-1, \(N(v_{n-1}) = \{u_{n-2}, v_n, v_{n-2}\}\), suffix is under modulo n and it can be observed that \(f(u_{n-1}) = 3\), \(f(v_n) = 4\), \(f(v_{n-2}) = 2\). Thus \(f(u_{n-1}) \neq f(v_n) \neq f(v_{n-2})\).
• 5. When i=n, \(N(u_n) = \{u_1, u_{n-1}, v_n\}\), suffix is under modulo n and it can be observed that \(f(u_1) = 1\), \(f(u_{n-1}) = 3\), \(f(v_n) = 4\). Thus \(f(u_1) \neq f(u_{n-1}) \neq f(v_n)\).
• 6. When i=n, \(N(v_n) = \{v_{n-1}, v_1, u_n\}\), suffix is under modulo n and also observe that \(f(v_{n-1}) = 3\), \(f(v_1) = 1\), \(f(u_n) = 4\). Thus \(f(v_{n-1}) \neq f(v_1) \neq f(u_n)\).

This proves that f is indeed an open neighborhood coloring and hence \(\chi_{onc}(G)=4\) for \(n\equiv 1\pmod 3\).

Case (3). \(n \equiv 2 \pmod{3}\).

For each k, \(0 \le k \le 2\), let \(S_k = \{u_i, v_i / i \equiv k \pmod{3}\}\) where \(1 \le i \le n-2\) be three \(P_3\) - independent sets of GP(n,1), constructed as mentioned in Lemma 3.4. Then, by lemma 3.3, for each k, \(0 \le k \le 2\), \(u_{n-1}, v_{n-1}, u_n, v_n \notin S_k\). For each k, \(0 \le k \le 2\), we may assign a single color to all the vertices of \(S_k\). Now vertices \(u_{n-1}, v_{n-1}, u_n, v_n\) are not assigned any color and hence at least one more color is required.

We now show that four colors are sufficient for an open neighborhood coloring of the prism in this case by considering three subcases.

Subcase (i). \(n \equiv 0, 2 \pmod{4}\)

Define the labeling \(f: V(G) \rightarrow Z^+\) as:

For all \[i\], \(1 \le i \le \frac{n}{2} - 1\),

\[f(v_i) = f(u_i) = \begin{cases} 1, & \text{if } i \equiv 1 \pmod{3}, \\ 2, & \text{if } i \equiv 2 \pmod{3}, \\ 3, & \text{if } i \equiv 0 \pmod{3}. \end{cases}\] for all \[i\], \(\frac{n}{2} + 1 \le i \le n - 1\)

\[f(v_i) = f(u_i) = \begin{cases} 1, & \text{if } i \equiv 2 \pmod{3}, \\ 2, & \text{if } i \equiv 0 \pmod{3}, \\ 3, & \text{if } i \equiv 1 \pmod{3}. \end{cases}\] and

\[f(u_n) = f(v_n) = f(u_{n/2}) = f(v_{n/2}) = 4.\]

We first consider the vertices in the inner polygon.

For all i, \(2 \le i \le \frac{n}{2} - 2\), \(N(u_i) = \{u_{i-1}, u_{i+1}, v_i\}\), where the suffix is under modulo n.

If \[i \equiv 1 \pmod{3}\] then \(f(u_{i-1}) = 3\), \(f(u_{i+1}) = 2\) and \(f(v_i) = 1\).

If \[i \equiv 2 \pmod{3}\] then \(f(u_{i-1}) = 1\), \(f(u_{i+1}) = 3\) and \(f(v_i) = 2\).

If \[i \equiv 0 \pmod{3}\] then \(f(u_{i-1}) = 2\), \(f(u_{i+1}) = 1\) and \(f(v_i) = 3\).

Hence for all \[i, 2 \le i \le \frac{n}{2} - 2\], \(f(u_{i-1}) \ne f(u_{i+1}) \ne f(v_i)\).

For all i, \(\frac{n}{2} + 2 \le i \le n - 2\), \(N(u_i) = \{u_{i-1}, u_{i+1}, v_i\}\), where the suffix is under modulo n.

If \[i \equiv 1 \pmod{3}\] then \(f(u_{i-1}) = 3\), \(f(u_{i+1}) = 2\) and \(f(v_i) = 1\).

If \[i \equiv 2 \pmod{3}\] then \(f(u_{i-1}) = 1\), \(f(u_{i+1}) = 3\) and \(f(v_i) = 2\).

If \[i \equiv 0 \pmod{3}\] then \(f(u_{i-1}) = 2\), \(f(u_{i+1}) = 1\) and \(f(v_i) = 3\).

Hence for all \[i, \frac{n}{2} + 2 \le i \le n - 2\], \(f(u_{i-1}) \ne f(u_{i+1}) \ne f(v_i)\).

We next consider the vertices in the outer polygon.

For all i, \(2 \le i \le \frac{n}{2} - 2\), \(N(v_i) = \{v_{i-1}, v_{i+1}, u_i\}\), where the suffix is under modulo n.

If \(i \equiv 1 \pmod{3}\) then \(f(v_{i-1}) = 3\), \(f(v_{i+1}) = 2\) and \(f(u_i) = 1\).

If \(i \equiv 2 \pmod{3}\) then \(f(v_{i-1}) = 1\), \(f(v_{i+1}) = 3\) and \(f(u_i) = 2\).

If \(i \equiv 0 \pmod{3}\) then \(f(v_{i-1}) = 2\), \(f(v_{i+1}) = 1\) and \(f(u_i) = 3\).

Hence for all \(i, 2 \le i \le \frac{n}{2} - 2\), \(f(v_{i-1}) \ne f(v_{i+1}) \ne f(u_i)\).

Also, for all i, \(\frac{n}{2} + 2 \le i \le n - 2\), \(N(v_i) = \{v_{i-1}, v_{i+1}, u_i\}\), where the suffix is under modulo n.

If \(i \equiv 1 \pmod{3}\) then \(f(v_{i-1}) = 3\), \(f(v_{i+1}) = 2\) and \(f(u_i) = 1\).

If \(i \equiv 2 \pmod{3}\) then \(f(v_{i-1}) = 1\), \(f(v_{i+1}) = 3\) and \(f(u_i) = 2\).

If \(i \equiv 0 \pmod{3}\) then \(f(v_{i-1}) = 2\), \(f(v_{i+1}) = 1\) and \(f(u_i) = 3\).

Hence for all \(i, \frac{n}{2} + 2 \le i \le n - 2, \ f(v_{i-1}) \ne f(v_{i+1}) \ne f(u_i).\)

Further for \(i = 1, n, n - 1, \frac{n}{2}, \frac{n}{2} + 1, \frac{n}{2} - 1\), we make the following observations:

• 1. When i=1, \(N(u_1) = \{u_2, u_n, v_1\}\), suffix is under modulo n and from the definition of f, we observe that \(f(u_2) = 2\), \(f(u_n) = 4\), \(f(v_1) = 1\). Thus \(f(u_2) \neq f(u_n) \neq f(v_1)\).
• 2. When i=1, \(N(v_1) = \{v_2, v_n, u_1\}\), suffix is under modulo n and it can be observed that \(f(u_1) = 1\), \(f(v_2) = 2\), \(f(v_n) = 4\). Thus \(f(v_1) \neq f(v_2) \neq f(v_n)\).
• 3. When i=n-1, \(N(u_{n-1}) = \{v_{n-1}, u_n, u_{n-2}\}\), suffix is under modulo n and we have \(f(v_{n-1}) = 3\), \(f(u_n) = 4\), \(f(u_{n-2}) = 2\). Thus \(f(v_{n-1}) \neq f(u_{n-1}) \neq f(u_n)\).
• 4. When i=n-1, \(N(v_{n-1}) = \{u_{n-2}, v_n, v_{n-2}\}\), suffix is under modulo n and it can be observed that \(f(u_{n-1}) = 3\), \(f(v_n) = 4\), \(f(v_{n-2}) = 2\). Thus \(f(u_{n-1}) \neq f(v_n) \neq f(v_{n-2})\).

• 5. When i=n, \(N(u_n) = \{u_1, u_{n-1}, v_n\}\), suffix is under modulo n and it can be observed that \(f(u_1) = 1\), \(f(u_{n-1}) = 3\), \(f(v_n) = 4\). Thus \(f(u_1) \neq f(u_n) \neq f(u_n)\).
• 6. When i=n, \(N(v_n) = \{v_{n-1}, v_1, u_n\}\), suffix is under modulo n and also observe that \(f(v_{n-1}) = 3\), \(f(v_1) = 1\), \(f(u_n) = 4\). Thus \(f(v_{n-1}) \neq f(v_1) \neq f(u_n)\).
• 7. When \(i = \frac{n}{2} 1\), \(N(u_{\frac{n}{2} 1}) = \left\{ u_{\frac{n}{2} 2}, u_{\frac{n}{2}}, v_{\frac{n}{2} 1} \right\}\), suffix is under modulo n and from the definition of f, we observe that \(f(u_{\frac{n}{2} 2}) = 2\), \(f(u_{\frac{n}{2}}) = 4\), \(f(v_{\frac{n}{2} 1}) = 3\). Thus \(f(u_{\frac{n}{2} 2}) \neq f(u_{\frac{n}{2}}) \neq f(v_{\frac{n}{2}})\).
• 8. When \(i = \frac{n}{2} 1\), \(N(v_{\frac{n}{2} 1}) = \left\{ v_{\frac{n}{2} 2}, v_{\frac{n}{2}}, u_{\frac{n}{2} 1} \right\}\), suffix is under modulo n and from the definition of f, we observe that \(f(v_{\frac{n}{2} 2}) = 2\), \(f(v_{\frac{n}{2}}) = 4\), \(f(u_{\frac{n}{2} 1}) = 3\). Thus \(f(v_{\frac{n}{2} 2}) \neq f(v_{\frac{n}{2}}) \neq f(u_{\frac{n}{2}})\).
• 9. When \(i = \frac{n}{2}\), \(N(u_{\frac{n}{2}}) = \left\{ u_{\frac{n}{2}-1}, u_{\frac{n}{2}+1}, v_{\frac{n}{2}} \right\}\), suffix is under modulo n and from the definition of f, we observe that \(f(u_{\frac{n}{2}-1}) = 3\), \(f(u_{\frac{n}{2}+1}) = 1\), \(f(v_{\frac{n}{2}}) = 4\). Thus \(f(u_{\frac{n}{2}-1}) \neq f(u_{\frac{n}{2}+1}) \neq f(v_{\frac{n}{2}})\).
• 10. When \(i = \frac{n}{2}\), \(N(v_{\frac{n}{2}}) = \left\{ v_{\frac{n}{2}-1}, v_{\frac{n}{2}+1}, u_{\frac{n}{2}} \right\}\), suffix is under modulo n and from the definition of f, we observe that \(f(v_{\frac{n}{2}-1}) = 3\), \(f(v_{\frac{n}{2}+1}) = 1\), \(f(u_{\frac{n}{2}}) = 4\). Thus \(f(v_{\frac{n}{2}-1}) \neq f(v_{\frac{n}{2}+1}) \neq f(u_{\frac{n}{2}})\).
• 11. When \(i = \frac{n}{2} + 1\), \(N(u_{\frac{n}{2} + 1}) = \left\{ u_{\frac{n}{2} + 2}, u_{\frac{n}{2}}, v_{\frac{n}{2} + 1} \right\}\), suffix is under modulo n and from the definition of f, we observe that \(f(u_{\frac{n}{2} + 2}) = 2\), \(f(u_{\frac{n}{2}}) = 4\), \(f(v_{\frac{n}{2} + 1}) = 1\). Thus \(f(u_{\frac{n}{2} + 2}) \neq f(u_{\frac{n}{2}}) \neq f(v_{\frac{n}{2} + 1})\).

12. When \(i = \frac{n}{2} + 1\), \(N(v_{\frac{n}{2} + 1}) = \left\{ v_{\frac{n}{2} + 2}, v_{\frac{n}{2}}, u_{\frac{n}{2} + 1} \right\}\), suffix is under modulo n and from the definition of f, we observe that \(f(v_{\frac{n}{2} + 2}) = 2\),

\[f(v_{n/2}) = 4, f(u_{n/2+1}) = 1.\] Thus \(f(v_{n/2+2}) \neq f(v_{n/2}) \neq f(u_{n/2+1}).\)

This proves that is f indeed an open neighborhood coloring and hence \(\chi_{onc}(G) = 4\) for \(n \equiv 2 \pmod{3}\) and \(n \equiv 0, 2 \pmod{4}\).

Subcase (ii). \(n \equiv 1 \pmod{4}\)

Define the labeling \(f:V(G) \to Z^+\) as:

For all \[i\], \(1 \le i \le \left\lceil \frac{n}{2} \right\rceil\) as

\[f(v_i) = f(u_i) = \begin{cases} 1, & \text{if } i \equiv 1 \pmod{3}, \\ 2, & \text{if } i \equiv 2 \pmod{3}, \\ 3, & \text{if } i \equiv 0 \pmod{3}. \end{cases}\] for all \[i\], \(\left\lceil \frac{n}{2} \right\rceil + 2 \le i \le n - 1\)

\[f(v_i) = f(u_i) = \begin{cases} 1, & \text{if } i \equiv 2 \pmod{3}, \\ 2, & \text{if } i \equiv 0 \pmod{3}, \\ 3, & \text{if } i \equiv 1 \pmod{3}. \end{cases}\] and

\[f(u_{\left\lceil \frac{n}{2} \right\rceil + 1}) = f(v_{\left\lceil \frac{n}{2} \right\rceil + 1}) = f(u_n) = f(v_n) = 4.\]

We first consider the vertices in the inner polygon.

For all \(i, 2 \le i \le \left\lceil \frac{n}{2} \right\rceil - 2\), \(N(u_i) = \{u_{i-1}, u_{i+1}, v_i\}\), where the suffix is under modulo n.

If \(i \equiv 1 \pmod{3}\) then \(f(u_{i-1}) = 3\), \(f(u_{i+1}) = 2\) and \(f(v_i) = 1\).

If \(i \equiv 2 \pmod{3}\) then \(f(u_{i-1}) = 1\), \(f(u_{i+1}) = 3\) and \(f(v_i) = 2\).

If \(i \equiv 0 \pmod{3}\) then \(f(u_{i-1}) = 2\), \(f(u_{i+1}) = 1\) and \(f(v_i) = 3\).

Hence for all \[i, 2 \le i \le \frac{n}{2} - 2\], \(f(u_{i-1}) \ne f(u_{i+1}) \ne f(v_i)\).

For all i, \(\left\lceil \frac{n}{2} \right\rceil + 2 \le i \le n - 2\), \(N(u_i) = \{u_{i-1}, u_{i+1}, v_i\}\), where the suffix is under modulo n.

If \(i \equiv 1 \pmod{3}\) then \(f(u_{i-1}) = 2\), \(f(u_{i+1}) = 1\) and \(f(v_i) = 3\).

If \(i \equiv 2 \pmod{3}\) then \(f(u_{i-1}) = 3\), \(f(u_{i+1}) = 2\) and \(f(v_i) = 1\).

If \(i \equiv 0 \pmod{3}\) then \(f(u_{i-1}) = 1\), \(f(u_{i+1}) = 3\) and \(f(v_i) = 2\).

Hence for all \[i, \frac{n}{2} + 1 \le i \le n - 2\], \(f(u_{i-1}) \ne f(u_{i+1}) \ne f(v_i)\).

We next consider the vertices in the outer polygon.

For all \[i\], \(2 \le i \le \left\lceil \frac{n}{2} \right\rceil - 2\), \(N(v_i) = \{v_{i-1}, v_{i+1}, u_i\}\), where the suffix is under modulo \(n\).

If \(i \equiv 1 \pmod{3}\) then \(f(v_{i-1}) = 3\), \(f(v_{i+1}) = 2\) and \(f(u_i) = 1\).

If \(i \equiv 2 \pmod{3}\) then \(f(v_{i-1}) = 1\), \(f(v_{i+1}) = 3\) and \(f(u_i) = 2\).

If \(i \equiv 0 \pmod{3}\) then \(f(v_{i-1}) = 2\), \(f(v_{i+1}) = 1\) and \(f(u_i) = 3\).

Hence for all \[i, 2 \le i \le \left\lceil \frac{n}{2} \right\rceil - 2\], \(f(v_{i-1}) \ne f(v_{i+1}) \ne f(u_i)\).

Also, for all i, \(\left\lceil \frac{n}{2} \right\rceil + 2 \le i \le n - 2\), \(N(v_i) = \{v_{i-1}, v_{i+1}, u_i\}\), where the suffix is under modulo n.

If \(i \equiv 1 \pmod{3}\) then \(f(v_{i-1}) = 2\), \(f(v_{i+1}) = 1\) and \(f(u_i) = 3\).

If \(i \equiv 2 \pmod{3}\) then \(f(v_{i-1}) = 1\), \(f(v_{i+1}) = 3\) and \(f(u_i) = 2\).

If \(i \equiv 0 \pmod{3}\) then \(f(v_{i-1}) = 1\), \(f(v_{i+1}) = 3\) and \(f(u_i) = 2\).

Hence for all \[i, \frac{n}{2} + 1 \le i \le n - 2, f(v_{i-1}) \ne f(v_{i+1}) \ne f(u_i).\]

Further for \(i = 1, n, n - 1, \left\lceil \frac{n}{2} \right\rceil, \left\lceil \frac{n}{2} \right\rceil + 2, \left\lceil \frac{n}{2} \right\rceil + 1\), we make the following observations:

1. When i=1, \(N(u_1) = \{u_2, u_n, v_1\}\), suffix is under modulo n and from the definition of f, we observe that \(f(u_2) = 2\), \(f(u_n) = 4\), \(f(v_1) = 1\). Thus \(f(u_2) \neq f(u_n) \neq f(v_1)\).

• 2. When i=1, \(N(v_1) = \{v_2, v_n, u_1\}\), suffix is under modulo n and it can be observed that \(f(u_1) = 1\), \(f(v_2) = 2\), \(f(v_n) = 4\). Thus \(f(v_1) \neq f(v_2) \neq f(v_n)\).
• 3. When i=n-1, \(N(u_{n-1}) = \{v_{n-1}, u_n, u_{n-2}\}\), suffix is under modulo n and we have \(f(v_{n-1}) = 3\), \(f(u_n) = 4\), \(f(u_{n-2}) = 2\). Thus \(f(v_{n-1}) \neq f(u_{n-1}) \neq f(u_n)\).
• 4. When i=n-1, \(N(v_{n-1}) = \{u_{n-1}, v_n, v_{n-2}\}\), suffix is under modulo n and it can be observed that \(f(u_{n-1}) = 3\), \(f(v_n) = 4\), \(f(v_{n-2}) = 2\). Thus \(f(u_{n-1}) \neq f(v_n) \neq f(v_{n-2})\).
• 5. When i=n, \(N(u_n) = \{u_1, u_{n-1}, v_n\}\), suffix is under modulo n and it can be observed that \(f(u_1) = 1\), \(f(u_{n-1}) = 3\), \(f(v_n) = 4\). Thus \(f(u_1) \neq f(u_{n-1}) \neq f(v_n)\).
• 6. When i=n, \(N(v_n) = \{v_{n-1}, v_1, u_n\}\), suffix is under modulo n and also observe that \(f(v_{n-1}) = 3\), \(f(v_1) = 1\), \(f(u_n) = 4\). Thus \(f(v_{n-1}) \neq f(v_1) \neq f(u_n)\).
• 7. When \(i = \left\lceil \frac{n}{2} \right\rceil\), \(N\left(u_{\left\lceil \frac{n}{2} \right\rceil}\right) = \left\{u_{\left\lceil \frac{n}{2} \right\rceil 1}, u_{\left\lceil \frac{n}{2} \right\rceil + 1}, v_{\left\lceil \frac{n}{2} \right\rceil}\right\}\), suffix is under modulo n and from the definition of f, we observe that \(f\left(u_{\left\lceil \frac{n}{2} \right\rceil 1}\right) = 2, f\left(u_{\left\lceil \frac{n}{2} \right\rceil + 1}\right) = 4, f\left(v_{\left\lceil \frac{n}{2} \right\rceil}\right) = 3\). Thus \(f\left(u_{\left\lceil \frac{n}{2} \right\rceil 1}\right) \neq f\left(u_{\left\lceil \frac{n}{2} \right\rceil 1}\right) \neq f\left(u_{\left\lceil \frac{n}{2} \right\rceil 1}\right) \neq f\left(u_{\left\lceil \frac{n}{2} \right\rceil 1}\right) \neq f\left(u_{\left\lceil \frac{n}{2} \right\rceil 1}\right)\)
• 8. When \(i = \left\lceil \frac{n}{2} \right\rceil\), \(N(v_{\lceil \frac{n}{2} \rceil}) = \left\{ v_{\lceil \frac{n}{2} \rceil}, v_{\lceil \frac{n}{2} \rceil + 1}, u_{\lceil \frac{n}{2} \rceil} \right\}\), suffix is under modulo n and from the definition of f, we observe that \(f(v_{\lceil \frac{n}{2} \rceil 1}) = 2, f(v_{\lceil \frac{n}{2} \rceil + 1}) = 4, f(u_{\lceil \frac{n}{2} \rceil 1}) = 3\). Thus \(f(v_{\lceil \frac{n}{2} \rceil 1}) \neq f(v_{\lceil \frac{n}{2} \rceil 1}) \neq f(u_{\lceil \frac{n}{2} \rceil + 1})\).

• 9. When \(i = \left\lceil \frac{n}{2} \right\rceil + 1\), \(N\left(u_{\left\lceil \frac{n}{2} \right\rceil + 1}\right) = \left\{u_{\left\lceil \frac{n}{2} \right\rceil}, u_{\left\lceil \frac{n}{2} \right\rceil + 2}, v_{\left\lceil \frac{n}{2} \right\rceil + 1}\right\}\), suffix is under modulo n and from the definition of f, we observe that \(f\left(u_{\left\lceil \frac{n}{2} \right\rceil}\right) = 3, f\left(u_{\left\lceil \frac{n}{2} \right\rceil + 2}\right) = 1, f\left(v_{\left\lceil \frac{n}{2} \right\rceil + 1}\right) = 4\). Thus \(f\left(u_{\left\lceil \frac{n}{2} \right\rceil}\right) \neq f\left(u_{\left\lceil \frac{n}{2} \right\rceil + 2}\right) \neq f\left(v_{\left\lceil \frac{n}{2} \right\rceil + 1}\right)\).
• 10. When \(i = \left\lceil \frac{n}{2} \right\rceil + 1\), \(N(v_{\left\lceil \frac{n}{2} \right\rceil + 1}) = \left\{ v_{\left\lceil \frac{n}{2} \right\rceil}, v_{\left\lceil \frac{n}{2} \right\rceil + 2}, u_{\left\lceil \frac{n}{2} \right\rceil + 1} \right\}\), suffix is under modulo n and from the definition of f, we observe that \(f(v_{\left\lceil \frac{n}{2} \right\rceil}) = 3, f(v_{\left\lceil \frac{n}{2} \right\rceil + 2}) = 1, f(u_{\left\lceil \frac{n}{2} \right\rceil + 1}) = 4\). Thus \(f(v_{\left\lceil \frac{n}{2} \right\rceil}) \neq f(v_{\left\lceil \frac{n}{2} \right\rceil + 2}) \neq f(u_{\left\lceil \frac{n}{2} \right\rceil})\).
• 11. When \(i = \left\lceil \frac{n}{2} \right\rceil + 2\), \(N\left(u_{\left\lceil \frac{n}{2} \right\rceil + 2}\right) = \left\{u_{\left\lceil \frac{n}{2} \right\rceil + 3}, u_{\left\lceil \frac{n}{2} \right\rceil + 1}, v_{\left\lceil \frac{n}{2} \right\rceil + 2}\right\}\), suffix is under modulo n and from the definition of f, we observe that \(f\left(u_{\left\lceil \frac{n}{2} \right\rceil + 3}\right) = 2, f\left(u_{\left\lceil \frac{n}{2} \right\rceil + 1}\right) = 4, f\left(v_{\left\lceil \frac{n}{2} \right\rceil + 2}\right) = 1\). Thus \(f\left(u_{\left\lceil \frac{n}{2} \right\rceil + 3}\right) \neq f\left(u_{\left\lceil \frac{n}{2} \right\rceil + 1}\right) \neq f\left(v_{\left\lceil \frac{n}{2} \right\rceil + 2}\right)\).
• 12. When \(i = \left\lceil \frac{n}{2} \right\rceil + 2\), \(N(v_{\left\lceil \frac{n}{2} \right\rceil + 2}) = \left\{ v_{\left\lceil \frac{n}{2} \right\rceil + 3}, v_{\left\lceil \frac{n}{2} \right\rceil + 1}, u_{\left\lceil \frac{n}{2} \right\rceil + 2} \right\}\), suffix is under modulo n and from the definition of f, we observe that \(f(v_{\left\lceil \frac{n}{2} \right\rceil + 3}) = 2\), \(f(v_{\left\lceil \frac{n}{2} \right\rceil + 1}) = 4\), \(f(u_{\left\lceil \frac{n}{2} \right\rceil + 2}) = 1\). Thus \(f(v_{\left\lceil \frac{n}{2} \right\rceil + 3}) \neq f(v_{\left\lceil \frac{n}{2} \right\rceil + 1}) \neq f(u_{\left\lceil \frac{n}{2} \right\rceil + 2})\).

This proves that is f indeed an open neighborhood coloring and hence \(\chi_{onc}(G)=4\) for \(n\equiv 2\pmod 3\) and \(n\equiv 1\pmod 4\).

Subcase (iii): \(n \equiv 3 \pmod{4}\).

Define the labeling \(f:V(G) \rightarrow Z^+\) as

\[f(v_i) = f(u_i) = \begin{cases} 1, & \text{if } i \equiv 1 \pmod{4}, \\ 2, & \text{if } i \equiv 2 \pmod{4}, \\ 3, & \text{if } i \equiv 3 \pmod{4}, \\ 4, & \text{if } i \equiv 0 \pmod{4} \end{cases}\]

We first consider the vertices of the inner polygon.

For all i, \(2 \le i \le n-2\), \(N(u_i) = \{u_{i-1}, u_{i+1}, v_i\}\), where the suffix is under modulo n.

If \[i \equiv 1 \pmod{4}\] then \(f(u_{i-1}) = 4\), \(f(u_{i+1}) = 2\) and \(f(v_i) = 1\).

If \[i \equiv 2 \pmod{4}\] then \(f(u_{i-1}) = 1\), \(f(u_{i+1}) = 3\) and \(f(v_i) = 2\).

If \[i \equiv 3 \pmod{4}\] then \(f(u_{i-1}) = 2\), \(f(u_{i+1}) = 4\) and \(f(v_i) = 3\).

If \[i \equiv 0 \pmod{4}\] then \(f(u_{i-1}) = 3\), \(f(u_{i+1}) = 1\) and \(f(v_i) = 4\).

Hence for all \[i, 2 \le i \le n-1\], \(f(u_{i-1}) \ne f(u_{i+1}) \ne f(v_i)\).

We now consider the vertices of the outer polygon.

For all \(i, 2 \le i \le n-2\), \(N(v_i) = \{v_{i-1}, v_{i+1}, u_i\}\), where the suffix is under modulo n.

If \[i \equiv 1 \pmod{4}\] then \(f(v_{i-1}) = 4\), \(f(v_{i+1}) = 2\) and \(f(u_i) = 1\).

If \[i \equiv 2 \pmod{4}\] then \(f(v_{i-1}) = 1\), \(f(v_{i+1}) = 3\) and \(f(u_i) = 2\).

If \[i \equiv 3 \pmod{4}\] then \(f(v_{i-1}) = 2\), \(f(v_{i+1}) = 4\) and \(f(u_i) = 3\).

If \[i \equiv 0 \pmod{4}\] then \(f(v_{i-1}) = 3\), \(f(v_{i+1}) = 1\) and \(f(u_i) = 4\).

Hence for all \[i, 2 \le i \le n-2\], \(f(v_{i-1}) \ne f(v_{i+1}) \ne f(u_i)\).

Further i = 1, n, n - 1, we make the following observations:

1. When i=1, \(N(u_1) = \{u_2, u_n, v_1\}\), suffix is under modulo n and from the definition of f, we observe that \(f(u_2) = 2\), \(f(u_n) = 3\), (since \(n \equiv 3 \pmod 4\)), \(f(v_1) = 1\). Thus \(f(u_2) \neq f(u_n) \neq f(v_1)\).

• 2. When i=1, \(N(v_1) = \{v_2, v_n, u_1\}\), suffix is under modulo n and it can be observed that \(f(u_1) = 1\), \(f(v_2) = 2\), \(f(v_n) = 3\). Thus \(f(v_1) \neq f(v_2) \neq f(v_n)\).
• 3. When i=n-1, \(N(u_{n-1}) = \{v_{n-1}, u_n, u_{n-2}\}\), suffix is under modulo n and we have \(f(v_{n-1}) = 2\), \(f(u_n) = 3\), \(f(u_{n-2}) = 1\). Thus \(f(v_{n-1}) \neq f(u_n) \neq f(u_n)\).
• 4. When i = n 1, \(N(v_{n-1}) = \{u_{n-1}, v_n, v_{n-2}\}\), suffix is under modulo n and it can be observed that \(f(u_{n-1}) = 2\), \(f(v_n) = 3\), \(f(v_{n-2}) = 1\). Thus \(f(u_{n-1}) \neq f(v_n) \neq f(v_{n-2})\).
• 5. When i=n, \(N(u_n) = \{u_1, u_{n-1}, v_n\}\), suffix is under modulo n and it can be observed that \(f(u_1) = 1\), \(f(u_{n-1}) = 2\), \(f(v_n) = 3\). Thus \(f(u_1) \neq f(u_{n-1}) \neq f(v_n)\).
• 6. When i=n, \(N(v_n) = \{v_{n-1}, v_1, u_n\}\), suffix is under modulo n and also observe that \(f(v_{n-1}) = 2\), \(f(v_1) = 1\), \(f(u_n) = 3\). Thus \(f(v_{n-1}) \neq f(v_1) \neq f(u_n)\).

This proves that f is indeed an open neighborhood coloring and hence \(\chi_{onc}(G) = 4\) for \(n \equiv 2 \pmod{3}\) and \(n \equiv 3 \pmod{4}\). Hence the theorem.

4 Conclusions

The open neighborhood coloring of some standard graphs like paths, cycles, trees, complete bipartite graph, triangular lattice has been determined in [4]. In this paper we have determined the open neighborhood coloring of the prism graph which is a particular case of the generalized Petersen's graph. The problem of determining the open neighborhood coloring of the generalized Petersen's graph is an open problem and we are working towards it. We are also working towards finding an upper bound for the open neighborhood chromatic number of any graph in terms of its maximum degree.

5 Open Problems

1. Determine the open neighborhood chromatic number of Generalized Petersen graph GP(n,1).

• 2. Determine the open neighborhood chromatic number of the Cartesian product of two graphs G¹ and . G²
• 3. Determine the open neighborhood chromatic number of the Strong product of two graphs G¹ and . G²
• 4. Determine the open neighborhood chromatic number of the Power of a graph , ^k G where k is a positive integer.