On the P₃ Coloring of Graphs

Abstract

The vertex coloring of graphs is a well-known coloring of graphs. In this coloring, all of the vertices are assigned colors in such a way that no two adjacent vertices have the same color. We can call this type of coloring $P_2$ coloring, where $P_2$ is a path graph. However, there are situations in which this type of coloring cannot give us the solution to the problem at hand. To answer such questions, in this article, we introduce a novel graph coloring called $P_3$ coloring. A graph is called $P_3$-colorable if we can assign colors to the vertices of the graph such that the vertices of every $P_3$ path are distinct. The minimum number of colors required for a graph to have $P_3$ coloring is called the $P_3$ chromatic number. The aim of this article is, in general, to prove some basic results concerning this coloring, and, in particular, to compute the $P_3$ chromatic number for different symmetric families of graphs.

1. Introduction

The history of graph coloring started with a problem that was about the maps of some countries, such as the United States. A map was to be colored in such a way that any two countries with the same border could not be colored with the same color. In 1971, an article entitled “The Mathematics of Map Coloring” was published in the Journal of Recreational Mathematics by H.S.M. (Donald) Coxeter, who proved that a “minimum of four colors are required for the map of United States to color the common border states differently” (see [1]). Since then, graph coloring has progressed immensely. When we talk about graph theory and its applications, one of the most commonly used, studied, and applicable topics in graph theory is graph coloring (see [2]). Graph coloring has many applications in various fields of life, such as timetabling (see, for example, [3,4,5,6]), scheduling daily life activities, scheduling computer processes (see [7,8]), registering allocations to different institutions and libraries (see [6,9,10]), manufacturing tools (see [11]), printed circuit testing (see [12]), routing and wavelength assignment (see [6]), bag rationalization for a food manufacturer (see [13]), satellite range scheduling (see [14,15]), and frequency assignment (see [6,16]). These are some applications out of the many that already exist and many to come. In fact, coloring has inspired many other fields of graph theory.

Coloring theory is the theory of dividing sets with internally compatible conflicts, and there are many different types of graph coloring; the history of graph coloring is provided in a previous survey [2]. There are numerous conjectures about coloring problems that are still unsolved and are being researched by mathematicians and computer scientists internationally; some of these are noted in [17]. There are many research articles being published about graph coloring. There are two types of categories of such articles: One category gives different colors to a graph according to the rules of the topic of the article, and the other is about the colored structures of graphs whose coloring cannot be controlled. For further reading and a literature review about graph coloring, readers can refer to [18,19,20,21]. A historical review and some recent developments in graph coloring schemes are presented in [22,23,24].

One way to understand the coloring of the vertices of a graph G is that we can see it as a function f from the vertex set of G to positive integers such that if $xy$ is an edge of G, then $f\left(x\right)\ne f\left(y\right)$. In other words, we assign colors to the vertices of G in such a way that adjacent vertices have different colors. This is called graph coloring or, more precisely, the vertex coloring of a graph. The minimum number of colors required for coloring a graph is called its chromatic number. Thus, in a sense, one can say that the assignment of colors to the vertices of a graph is called graph coloring if the colors of the vertices of all $P_2$ paths in the graph are distinct; that is, instead of using the word “edge”, we can use the term “$P_2$ path”.

Therefore, in this article, motivated by the above reasoning, we introduce the $P_3$-labeling of graphs, and we will discuss this labeling for some very well-known families of graphs, such as path graphs, wheel graphs, cycle graphs, complete graphs, prism graphs, ladder graphs, and star graphs.

Definition 1. 

A $P_3$ coloring is a function f from the vertex set of G to the set of colors $\{c_1,c_2,c_3,\dots ,$$c_k\}$ such that for every $P_3$ path on graph G, the colors of its vertices are distinct, that is, if $xyz$ is a $P_3$ path on G, then $f\left(x\right)\ne f\left(y\right)\ne f\left(z\right)\ne f\left(x\right)$. This is a natural generalization of $P_2$ coloring.

Definition 2. 

The minimum number of colors required for a graph G to have $P_3$ coloring is called the $P_3$ chromatic number, and it is denoted as ${\chi }_3\left(G\right)$.

Note that every $P_3$ coloring of a graph is also its $P_2$ coloring. Therefore, we have

$$\chi \left(G\right)\le {\chi }_3\left(G\right).$$

(1)

In addition, it is clear from the definition that for all graphs G,

$${\chi }_3\left(G\right)\ge 3.$$

(2)

2. Motivation

To place more emphasis on the motivation for our introduction of this type of coloring, here, we will give an example in which we cannot apply $P_2$ coloring, but only $P_3$ coloring. In addition, much in the field of mathematics is produced by the curiosity of the minds of mathematicians when a question emerges while discussing something. In the field of computer science, there are graphs that are associated with bit strings. Suppose that we have a set S consisting of all bit strings of length $n>1$. Then, a hypercube graph, which is also known as a cube graph and denoted as $Q_n$, is a graph consisting of the elements of S as vertices, and there is an edge between two strings if they differ at exactly one position. Now, if we want to assign different colors to the strings that are different by at most two positions (or someone challenges us to color the strings (vertices) of $Q_n$ in such a way that any two strings that differ by at most two positions have different colors), then what type of coloring will we use? Moreover, what is the minimum number of colors required to achieve this? It is very easy to see that we cannot use $P_2$ coloring here, and we have to apply $P_3$ coloring to find a possible solution. For example, in Figure 1, we can see that the usual $P_2$ coloring of $Q_2$ requires only two colors to color this graph, but for the above question, we cannot color it with two colors. For this purpose, we have to use $P_3$ coloring, which gives us the solution with four colors for $Q_2$. For the case in which $n\ge 3$, ${\chi }_3\left(Q_n\right)$ is given in the section of this article on open questions.

3. Main Results

In this section, we present the main results of this article. Theorem 1, Lemma 1, and its corollaries give us the $P_3$ chromatic number of some general graphs. In Theorems 2–5, closed formulas are found for the $P_3$ chromatic number of path graphs, cycle graphs, prism graphs, and ladder graphs. The next theorem gives us the $P_3$ chromatic number of path graph.

Lemma 1. 

Let G be a simple graph on n vertices and assume that there is a vertex $v\in V\left(G\right)$ such that v is adjacent to every vertex of G, then ${\chi }_3\left(G\right)=n$.

Proof. 

By contrast, suppose that ${\chi }_{P_3}\left(G\right)<n$. This means that there are two vertices in G having the same color, e.g., $x,y$ are those vertices. However, every two vertices of G are on some $P_3$ path having v as the middle vertex. Thus, we have a $P_3$ path $xvy$, and this path has the same color as that of its end vertices. This is a contradiction. Therefore, ${\chi }_3\left(G\right)$ must be $\left|V\right(G\left)\right|$. □

The following corollaries directly result from the Lemma 1:

Corollary 1. 

Let $K_n$ be the complete graph then ${\chi }_3\left(K_n\right)=n$ for all $n\ge 3$;

Corollary 2. 

Let $W_n$ be the wheel graph on n vertices, then ${\chi }_3\left(W_n\right)=n$ for all $n\ge 4$;

Corollary 3. 

Let $S_n$ be the star graph on n vertices, then ${\chi }_3\left(S_n\right)=n$ for all $n\ge 3$.

The following Theorem 1 also follows from the above definition:

Theorem 1. 

Let G be a graph and H be a subgraph of G then ${\chi }_3\left(G\right)\ge {\chi }_3\left(H\right)$;

Theorem 2. 

Let $P_n$ be the path graph, then ${\chi }_3\left(P_n\right)=3$ for all $n\ge 3$;

Proof. 

Let $P_n$ be a path graph on n vertices, where $n\ge 3$ as shown in Figure 2.

To show that ${\chi }_{P_3}\left(P_n\right)=3$, first, we show that the path graph has $P_3$ coloring. For this purpose, we define a function from the set of vertices of $P_n$ to the set of colors $\{0,1,2\}$. Thus, lets define a function as follows:

$$f\left(x_i\right)=\left\{\begin{array}{cc}0,\hfill & \mathrm{if}i\equiv 0\left(\mathrm{mod}3\right);\hfill \\ 1,\hfill & \mathrm{if}i\equiv 1\left(\mathrm{mod}3\right);\hfill \\ 2,\hfill & \mathrm{if}i\equiv 2\left(\mathrm{mod}3\right).\hfill \end{array}\right.$$

To prove that f is indeed a $P_3$ coloring, we show that all $P_3$ paths in $P_n$ are of different colors. Let Q be a $P_3$ path in $P_n$ as depicted in Figure 3; then, there are three possible cases.

• Case I: If $j\equiv 0\left(\mathrm{mod}3\right)$, then $f\left(x_j\right)=0,f\left(x_{j+1}\right)=1,f\left(x_{j+2}\right)=2$;
• Case II: If $j\equiv 1\left(\mathrm{mod}3\right)$, then $f\left(x_{i+1}\right)=1,f\left(x_{i+2}\right)=2,f\left(x_{i+3}\right)=0$;
• Case III: If $j\equiv 2\left(\mathrm{mod}3\right)$, then $f\left(x_{i+2}\right)=2,f\left(x_{i+3}\right)=0,f\left(x_{i+4}\right)=1$.

Thus, from all of the above possible cases, we can see that all $P_3$ paths Q have different colors of its vertices under the labeling f. Thus, f is a $P_3$ coloring and by using Equation (2), we reach our conclusion that is $ch{i}_{P_3}\left(P_n\right)=3$. □

Theorem 3. 

Let $C_n$ be the cycle graph and $n\ne 5$. Then, for all $n\ge 3$

$${\chi }_3\left(C_n\right)=\left\{\begin{array}{cc}3,\hfill & n\equiv 0\left(\mathrm{mod}3\right);\hfill \\ 4,\hfill & n\equiv 2\left(\mathrm{mod}3\right).\hfill \end{array}\right.$$

Proof. 

Let $C_n$ be the cycle graph on n vertices and $n\ge 3$. This proof consists of three cases on three different values of n under $\mathrm{mod}3$.

• Case I: Suppose that $n\equiv 0\left(\mathrm{mod}3\right)$. Let us define a function f on the vertices of $C_n$ as follows:

  $$f\left(x_i\right)=\left\{\begin{array}{cc}1,\hfill & \mathrm{if}i\equiv 0\left(\mathrm{mod}3\right);\hfill \\ 2,\hfill & \mathrm{if}i\equiv 1\left(\mathrm{mod}3\right);\hfill \\ 3,\hfill & \mathrm{if}i\equiv 2\left(\mathrm{mod}3\right),\hfill \end{array}\right.$$

  where $1\le i\le n-4$. Figure 4 represents the $P_3$ coloring of $C_9$ to explain this labeling. Let $Q_1:x_i{x}_{i+1}{x}_{i+2}$ be an arbitrary $P_3$ path in $C_n$, as shown in Figure 5, for $0\le i\le n-1$.
  Then, there are three possible cases.

  (a). 

  From Figure 5, we have,

  if $i\equiv 0\left(\mathrm{mod}3\right)$, then $f\left(x_i\right)=1,f\left(x_{i+1}\right)=2,f\left(x_{i+2}\right)=3$;

  (b). 

  If $i\equiv 1\left(\mathrm{mod}3\right)$, then $f\left(x_i\right)=2,f\left(x_{i+1}\right)=3,f\left(x_{i+2}\right)=1$;

  (c). 

  If $i\equiv 2\left(\mathrm{mod}3\right)$, then $f\left(x_i\right)=3,f\left(x_{i+1}\right)=1,f\left(x_{i+2}\right)=2$.

  Thus, from all of these cases, we can see that all $P_3$ paths have different colors of their vertices. Thus, f is a $P_3$ coloring, and the result follows.
• Case II: Suppose that $n\equiv 1\left(\mathrm{mod}3\right)$. In this case, when we start a $P_3$ coloring of $C_n$ from any vertex, e.g., $x_1$, to the last, e.g., $x_n$, with at most three colors, then the last vertex $x_n$ cannot be assigned any color from the given three colors. Thus, we need at least four colors to have a $P_3$ coloring of this graph. For the reverse case, we define the $P_3$-labeling function as follows:
  $f\left(x_n\right)=1,f\left(x_{n-1}\right)=2,f\left(x_{n-2}\right)=3,f\left(x_{n-3}\right)=4$ and for all $1\le i\le n-4$ we have

  $$f\left(x_i\right)=\left\{\begin{array}{cc}4,\hfill & \mathrm{if}i\equiv 1\left(\mathrm{mod}3\right);\hfill \\ 3,\hfill & \mathrm{if}i\equiv 2\left(\mathrm{mod}3\right);\hfill \\ 2,\hfill & \mathrm{if}i\equiv 0\left(\mathrm{mod}3\right).\hfill \end{array}\right.$$
  Figure 6 represents the $P_3$ coloring of $C_{10}$ to explain this labeling. Let $Q_2$ be an arbitrary path $x_i{x}_{i+1}{x}_{i+2}$ in $C_n$; then, there are four possible cases to discuss this labeling.

  (a). 

  If $i\equiv 0\left(\mathrm{mod}3\right)$, then $f\left(x_i\right)=2,f\left(x_{i+1}\right)=4,f\left(x_{i+2}\right)=3$;

  (b). 

  If $i\equiv 1\left(\mathrm{mod}3\right)$, then $f\left(x_i\right)=4,f\left(x_{i+1}\right)=3,f\left(x_{i+2}\right)=2$;

  (c). 

  If $i\equiv 2\left(\mathrm{mod}3\right)$, then $f\left(x_i\right)=3,f\left(x_{i+1}\right)=2,f\left(x_{i+2}\right)=4$;

  (d). 

  When the paths are of the forms $x_1{x}_2{x}_n$, $x_1{x}_n{x}_{n-1}$, $x_{n-2}{x}_{n-3}{x}_{n-4}$ and $x_{n-3}{x}_{n-4}{x}_{n-5}$;

  (i) 

  For the path $x_1{x}_2{x}_n$, we have the labeling $f\left(x_1\right)=4,f\left(x_2\right)=3,f\left(x_n\right)=1$;

  (ii) 

  For the path $x_1{x}_n{x}_{n-1}$, we have the labeling $f\left(x_1\right)=4,f\left(x_n\right)=1,f\left(x_{n-1}\right)=2$;

  (iii) 

  For the path $x_{n-2}{x}_{n-3}{x}_{n-4}$, we have the labeling $f\left(x_{n-2}\right)=3,f\left(x_{n-3}\right)=4,f\left(x_{n-4}\right)=2$ because $n\equiv 1\left(\mathrm{mod}3\right)$;

  (iv) 

  For the path $x_{n-3}{x}_{n-4}{x}_{n-5}$, we have the labeling $f\left(x_{n-3}\right)=4,f\left(x_{n-4}\right)=2,f\left(x_{n-5}\right)=3$ because $n\equiv 1\left(\mathrm{mod}3\right)$.

  Thus, from all of these cases, we can see that all $P_3$ paths have different colors of their vertices. Thus, f is indeed a $P_3$ coloring. This shows that ${\chi }_{P_3}\left(C_n\right)\le 4$. This concludes the result.

• Case III: When $n\equiv 2\left(\mathrm{mod}3\right)$. In this case, to start a $P_3$ coloring of $C_n$ from vertex $x_1$ to the last with at most three colors, the last two vertices $x_{n-1}$, $x_n$ cannot be assigned any color from the given three colors. Therefore, we need at least four colors to have $P_3$ coloring of this graph. For the reverse case, we will define $P_3$ labeling function as follows:
  $f\left(x_1\right)=1,f\left(x_2\right)=2$, $f\left(x_3\right)=3,f\left(x_4\right)=4$, $f\left(x_n\right)=4,f\left(x_{n-1}\right)=3$, $f\left(x_{n-2}\right)=2,f\left(x_{n-3}\right)=1$, and for all $5\le i\le n-4$, the function is defined by

  $$f\left(x_i\right)=\left\{\begin{array}{cc}2,\hfill & \mathrm{if}i\equiv 2\left(\mathrm{mod}3\right);\hfill \\ 3,\hfill & \mathrm{if}i\equiv 0\left(\mathrm{mod}3\right);\hfill \\ 4,\hfill & \mathrm{if}i\equiv 1\left(\mathrm{mod}3\right).\hfill \end{array}\right.$$
  To explain this labeling, Figure 7 shows a $P_3$ coloring of $C_{11}$ under f. Let $Q_3$ be any arbitrary $P_3$ path in $C_n$; then, we have the following cases to discuss for the assertion of $P_3$ coloring.

  (a). 

  If $i\equiv 0\left(\mathrm{mod}3\right)$ and $5\le i\le n-4$, then $f\left(x_i\right)=3,f\left(x_{i+1}\right)=4,f\left(x_{i+2}\right)=2$;

  (b). 

  If $i\equiv 1\left(\mathrm{mod}3\right)$ and $5\le i\le n-4$, then $f\left(x_i\right)=4,f\left(x_{i+1}\right)=2,f\left(x_{i+2}\right)=3$;

  (c). 

  If $i\equiv 2\left(\mathrm{mod}3\right)$ and $5\le i\le n-4$, then $f\left(x_i\right)=2,f\left(x_{i+1}\right)=3,f\left(x_{i+2}\right)=4$;

  (d). 

  For the following paths, we have different labeling:

  (i) 

  For path $x_3{x}_4{x}_5$, we have the labeling $f\left(x_3\right)=3,f\left(x_4\right)=4,f\left(x_5\right)=2$;

  (ii) 

  For path $x_4{x}_5{x}_6$, we have the labeling $f\left(x_4\right)=4,f\left(x_5\right)=2,f\left(x_6\right)=3$;

  (iii) 

  For path $x_{n-2}{x}_{n-3}{x}_{n-4}$, we have the labeling $f\left(x_{n-2}\right)=2,f\left(x_{n-3}\right)=1$, $f\left(x_{n-4}\right)=4$ because $n\equiv 2\left(\mathrm{mod}3\right)$;

  (iv) 

  For path $x_{n-3}{x}_{n-4}{x}_{n-5}$, we have the labeling $f\left(x_{n-3}\right)=1,f\left(x_{n-4}\right)=4$, $f\left(x_{n-5}\right)=3$ because $n\equiv 2\left(\mathrm{mod}3\right)$.

  Therefore, from all of these cases, we can see that all $P_3$ paths have different colors of their vertices. Thus, f is a $P_3$ coloring and ${\chi }_3\left(C_n\right)\le 4$ for all $n\ge 8$. Hence, the proof is completed.

□

Remark 1. 

The ${\chi }_3\left(C_5\right)=5$, and it is very easy to see that we cannot have $P_3$-coloring of $C_5$ with less than 5 colors.

Remark 2. 

Note that for ${\chi }_3\left(C_n\right)=3={\chi }_3\left(C_n\right)$ for $n=3$ and ${\chi }_3\left(P_n\right)=3>2=\chi \left(P_n\right)$ this shows that for some graphs, the $P_3$-chromatic number is equal to their chromatic number, and for some graphs, this relation is strict.

Theorem 4. 

Let $G\cong D_n$ be the prism graph. Then

$${\chi }_3\left(D_n\right)=\left\{\begin{array}{cc}4,\hfill & \mathrm{if}n\equiv 0\left(\mathrm{mod}4\right)\mathrm{and}n\ge 4;\hfill \\ 5,\hfill & \mathrm{if}n\equiv 1\left(\mathrm{mod}4\right)\mathrm{and}n\ge 9;\hfill \\ 5,\hfill & \mathrm{if}n\equiv 2\left(\mathrm{mod}4\right)\mathrm{and}n\ge 10;\hfill \\ 5,\hfill & \mathrm{if}n\equiv 3\left(\mathrm{mod}4\right)\mathrm{and}n\ge 15.\hfill \end{array}\right.$$

Proof. 

Let $D_n$ be the prism graph as depicted in Figure 8. We shall discuss the proof in four cases.

• Case I. Assume that $n\equiv 0\left(\mathrm{mod}4\right)$ and $n\ge 4$. Since $C_4$ is a subgraph of $D_n$, then from Theorem 1, we have ${\chi }_3\left(D_n\right)\ge 4$. To prove the reverse, we shall define a function $g:V\left(Dn\right)\to \{1,2,3,4\}$ as follows:

  $$g\left({\alpha }_i\right)=\left\{\begin{array}{cc}1,\hfill & \mathrm{if}i\equiv 1\left(\mathrm{mod}4\right),1\le i\le n;\hfill \\ 2,\hfill & \mathrm{if}i\equiv 2\left(\mathrm{mod}4\right),1\le i\le n;\hfill \\ 3,\hfill & \mathrm{if}i\equiv 3\left(\mathrm{mod}4\right),1\le i\le n;\hfill \\ 4,\hfill & \mathrm{if}i\equiv 0\left(\mathrm{mod}4\right),1\le i\le n.\hfill \end{array}\right.$$

  $$g\left({\beta }_i\right)=\left\{\begin{array}{cc}3,\hfill & \mathrm{if}i\equiv 1\left(\mathrm{mod}4\right),1\le i\le n;\hfill \\ 4,\hfill & \mathrm{if}i\equiv 2\left(\mathrm{mod}4\right),1\le i\le n;\hfill \\ 1,\hfill & \mathrm{if}i\equiv 3\left(\mathrm{mod}4\right),1\le i\le n;\hfill \\ 2,\hfill & \mathrm{if}i\equiv 0\left(\mathrm{mod}4\right),1\le i\le n.\hfill \end{array}\right.$$
  We will show that f is a $P_3$ coloring. Let $Q_1$ be any arbitrary $P_3$ path in $D_n$; then, there are ten possible types of $P_3$ paths in $D_n$, and they are as follows: The paths are ${\alpha }_i{\alpha }_{i+1}{a}_{i+2}$, ${\alpha }_i{\alpha }_{i+1}{\beta }_{i+1}$, ${\alpha }_i{\beta }_i{\beta }_{i+1}$, ${\beta }_i{\beta }_{i+1}{b}_{i+2}$, ${\beta }_i{\alpha }_i{\alpha }_{i+1}$, ${\beta }_i{\beta }_{i+1}{\alpha }_{i+1}$, ${\alpha }_{i+1}{\alpha }_{i+2}{\beta }_{i+2}$, ${\beta }_{i+1}{\alpha }_{i+1}{\alpha }_{i+2}$, ${\alpha }_{i+2}{\beta }_{i+2}{\beta }_{i+1}$ and ${\beta }_{i+2}{\beta }_{i+1}{\alpha }_{i+1}$.

  (a). 

  For $i\equiv 0\left(\mathrm{mod}4\right)$, we have ten possibilities of the induced coloring of $Q_1$ from g as follows:

  (i) 

  If the path is ${\alpha }_i{\alpha }_{i+1}{\alpha }_{i+2}$, then we have $g\left({\alpha }_i\right)=4,g\left({\alpha }_{i+1}\right)=1,g\left({\alpha }_{i+2}\right)=2$;

  (ii) 

  If the path is ${\alpha }_i{\alpha }_{i+1}{\beta }_{i+1}$, then we have $g\left({\alpha }_i\right)=4,g\left({\alpha }_{i+1}\right)=1,g\left({\beta }_{i+1}\right)=3$;

  (iii) 

  If the path is ${\alpha }_i{b}_i{\beta }_{i+1}$, then we have $g\left({\alpha }_i\right)=4,g\left({\beta }_i\right)=2,g\left({\beta }_{i+1}\right)=3$;

  (iv) 

  If the path is ${\beta }_i{\beta }_{i+1}{\beta }_{i+2}$, then we have $g\left({\beta }_i\right)=2,g\left({\beta }_{i+1}\right)=3,g\left({\beta }_{i+2}\right)=4$;

  (v) 

  If the path is ${\beta }_i{a}_i{\alpha }_{i+1}$, then we have $g\left({\beta }_i\right)=2,g\left({\alpha }_i\right)=4,g\left({\alpha }_{i+1}\right)=1$;

  (vi) 

  If the path is ${\beta }_i{\beta }_{i+1}{\alpha }_{i+1}$, then we have $g\left({\beta }_i\right)=2,g\left({\beta }_{i+1}\right)=3,g\left({\alpha }_{i+1}\right)=1$;

  (vii) 

  If the path is ${\alpha }_{i+1}{\alpha }_{i+2}{\beta }_{i+2}$, then we have $g\left({\alpha }_{i+1}\right)=1,g\left({\alpha }_{i+2}\right)=2,g\left({\beta }_{i+2}\right)=3$;

  (viii) 

  If the path is ${\beta }_{i+1}{\alpha }_{i+1}{\alpha }_{i+2}$, then we have $g\left({\beta }_{i+1}\right)=3,g\left({\alpha }_{i+1}\right)=1,g\left({\alpha }_{i+2}\right)=2$;

  (ix) 

  If the path is ${\alpha }_{i+2}{\beta }_{i+2}{\beta }_{i+1}$, then we have $g\left({\alpha }_{i+2}\right)=2,g\left({\beta }_{i+2}\right)=4,g\left({\beta }_{i+1}\right)=3$;

  (x) 

  If the path is ${\beta }_{i+2}{\beta }_{i+1}{\alpha }_{i+1}$, then we have $g\left({\beta }_{i+2}\right)=4,g\left({\beta }_{i+1}\right)=3,g\left({\alpha }_{i+1}\right)=1$.

  (b). 

  For $i\equiv 1\left(\mathrm{mod}4\right)$, we have ten possibilities of the induced coloring of $Q_1$ from g as follows:

  (i) 

  If the path is ${\alpha }_i{\alpha }_{i+1}{\alpha }_{i+2}$, then we have $g\left({\alpha }_i\right)=1,g\left({\alpha }_{i+1}\right)=2,g\left({\alpha }_{i+2}\right)=3$;

  (ii) 

  If the path is ${\alpha }_i{\alpha }_{i+1}{\beta }_{i+1}$, then we have $g\left({\alpha }_i\right)=1,g\left({\alpha }_{i+1}\right)=2,g\left({\beta }_{i+1}\right)=4$;

  (iii) 

  If the path is ${\alpha }_i{b}_i{\beta }_{i+1}$, then we have $g\left({\alpha }_i\right)=1,g\left({\beta }_i\right)=3,g\left({\beta }_{i+1}\right)=4$;

  (iv) 

  If the path is ${\beta }_i{\beta }_{i+1}{\beta }_{i+2}$, then we have $g\left({\beta }_i\right)=3,g\left({\beta }_{i+1}\right)=4,g\left({\beta }_{i+2}\right)=1$;

  (v) 

  If the path is ${\beta }_i{a}_i{\alpha }_{i+1}$, then we have $g\left({\beta }_i\right)=3,g\left({\alpha }_i\right)=1,g\left({\alpha }_{i+1}\right)=2$;

  (vi) 

  If the path is ${\beta }_i{\beta }_{i+1}{\alpha }_{i+1}$, then we have $g\left({\beta }_i\right)=3,g\left({\beta }_{i+1}\right)=4,g\left({\alpha }_{i+1}\right)=2$;

  (vii) 

  If the path is ${\alpha }_{i+1}{\alpha }_{i+2}{\beta }_{i+2}$, then we have $g\left({\alpha }_{i+1}\right)=4,g\left({\alpha }_{i+2}\right)=3$, $g\left({\beta }_{i+2}\right)=1$;

  (viii) 

  If the path is ${\beta }_{i+1}{\alpha }_{i+1}{\alpha }_{i+2}$, then we have $g\left({\beta }_{i+1}\right)=4,g\left({\alpha }_{i+1}\right)=2$, $g\left({\alpha }_{i+2}\right)=3$;

  (ix) 

  If the path is ${\alpha }_{i+2}{\beta }_{i+2}{\beta }_{i+1}$, then we have $g\left({\alpha }_{i+2}\right)=2,g\left({\beta }_{i+2}\right)=1$, $g\left({\beta }_{i+1}\right)=4$;

  (x) 

  If the path is ${\beta }_{i+2}{\beta }_{i+1}{\alpha }_{i+1}$, then we have $g\left({\beta }_{i+2}\right)=1,g\left({\beta }_{i+1}\right)=4$, $g\left({\alpha }_{i+1}\right)=2$.

  (c). 

  For $i\equiv 2\left(\mathrm{mod}4\right)$, we again have ten possibilities of the induced coloring of $Q_1$ from g as follows:

  (i) 

  If the path is ${\alpha }_i{\alpha }_{i+1}{\alpha }_{i+2}$, then we have $g\left({\alpha }_i\right)=2,g\left({\alpha }_{i+1}\right)=3,g\left({\alpha }_{i+2}\right)=4$;

  (ii) 

  If the path is ${\alpha }_i{\alpha }_{i+1}{\beta }_{i+1}$, then we have $g\left({\alpha }_i\right)=2,g\left({\alpha }_{i+1}\right)=3,g\left({\beta }_{i+1}\right)=1$;

  (iii) 

  If the path is ${\alpha }_i{b}_i{\beta }_{i+1}$, then we have $g\left({\alpha }_i\right)=2,g\left({\beta }_i\right)=4,g\left({\beta }_{i+1}\right)=1$;

  (iv) 

  If the path is ${\beta }_i{\beta }_{i+1}{\beta }_{i+2}$, then we have $g\left({\beta }_i\right)=4,g\left({\beta }_{i+1}\right)=1,g\left({\beta }_{i+2}\right)=2$;

  (v) 

  If the path is ${\beta }_i{a}_i{\alpha }_{i+1}$, then we have $g\left({\beta }_i\right)=4,g\left({\alpha }_i\right)=2,g\left({\alpha }_{i+1}\right)=3$;

  (vi) 

  If the path is ${\beta }_i{\beta }_{i+1}{\alpha }_{i+1}$, then we have $g\left({\beta }_i\right)=4,g\left({\beta }_{i+1}\right)=1,g\left({\alpha }_{i+1}\right)=3$;

  (vii) 

  If the path is ${\alpha }_{i+1}{\alpha }_{i+2}{\beta }_{i+2}$, then we have $g\left({\alpha }_{i+1}\right)=3,g\left({\alpha }_{i+2}\right)=4$, $g\left({\beta }_{i+2}\right)=2$;

  (viii) 

  If the path is ${\beta }_{i+1}{\alpha }_{i+1}{\alpha }_{i+2}$, then we have $g\left({\beta }_{i+1}\right)=1,g\left({\alpha }_{i+1}\right)=3$, $g\left({\alpha }_{i+2}\right)=4$;

  (ix) 

  If the path is ${\alpha }_{i+2}{\beta }_{i+2}{\beta }_{i+1}$, then we have $g\left({\alpha }_{i+2}\right)=4,g\left({\beta }_{i+2}\right)=2$, $g\left({\beta }_{i+1}\right)=1$;

  (x) 

  If the path is ${\beta }_{i+2}{\beta }_{i+1}{\alpha }_{i+1}$, then we have $g\left({\beta }_{i+2}\right)=2,g\left({\beta }_{i+1}\right)=1$, $g\left({\alpha }_{i+1}\right)=3$.

  (d). 

  For $i\equiv 3\left(\mathrm{mod}4\right)$, we have ten possibilities of the induced coloring of $Q_1$ from g as follows:

  (i) 

  If the path is ${\alpha }_i{\alpha }_{i+1}{\alpha }_{i+2}$, then we have $g\left({\alpha }_i\right)=3,g\left({\alpha }_{i+1}\right)=4,g\left({\alpha }_{i+2}\right)=1$;

  (ii) 

  If the path is ${\alpha }_i{\alpha }_{i+1}{\beta }_{i+1}$, then we have $g\left({\alpha }_i\right)=3,g\left({\alpha }_{i+1}\right)=4,g\left({\beta }_{i+1}\right)=2$;

  (iii) 

  If the path is ${\alpha }_i{b}_i{\beta }_{i+1}$, then we have $g\left({\alpha }_i\right)=3,g\left({\beta }_i\right)=1,g\left({\beta }_{i+1}\right)=2$;

  (iv) 

  If the path is ${\beta }_i{\beta }_{i+1}{\beta }_{i+2}$, then we have $g\left({\beta }_i\right)=1,g\left({\beta }_{i+1}\right)=2,g\left({\beta }_{i+2}\right)=3$;

  (v) 

  If the path is ${\beta }_i{a}_i{\alpha }_{i+1}$, then we have $g\left({\beta }_i\right)=1,g\left({\alpha }_i\right)=3,g\left({\alpha }_{i+1}\right)=4$;

  (vi) 

  If the path is ${\beta }_i{\beta }_{i+1}{\alpha }_{i+1}$, then we have $g\left({\beta }_i\right)=1,g\left({\beta }_{i+1}\right)=3,g\left({\alpha }_{i+1}\right)=4$;

  (vii) 

  If the path is ${\alpha }_{i+1}{\alpha }_{i+2}{\beta }_{i+2}$, then we have $g\left({\alpha }_{i+1}\right)=4,g\left({\alpha }_{i+2}\right)=1$, $g\left({\beta }_{i+2}\right)=3$;

  (viii) 

  If the path is ${\beta }_{i+1}{\alpha }_{i+1}{\alpha }_{i+2}$, then we have $g\left({\beta }_{i+1}\right)=2,g\left({\alpha }_{i+1}\right)=4$, $g\left({\alpha }_{i+2}\right)=1$;

  (ix) 

  If the path is ${\alpha }_{i+2}{\beta }_{i+2}{\beta }_{i+1}$, then we have $g\left({\alpha }_{i+2}\right)=1,g\left({\beta }_{i+2}\right)=3$, $g\left({\beta }_{i+1}\right)=2$;

  (x) 

  If the path is ${\beta }_{i+2}{\beta }_{i+1}{\alpha }_{i+1}$, then we have $g\left({\beta }_{i+2}\right)=3,g\left({\beta }_{i+1}\right)=2$, $g\left({\alpha }_{i+1}\right)=4$.

  In all of these subcases, we can see that g is indeed a $P_3$ coloring. Therefore, the $P_3$-chromatic number of prism graph $D_n$ is 4 for all $n\ge 4$ and $n\equiv 0\left(\mathrm{mod}4\right)$.
• Case II. Assume that $n\equiv 1\left(\mathrm{mod}4\right)$ and $n\ge 9$. Note that in any $P_3$ coloring, if we color the vertices of the $D_n$ graph from a set of only four colors $\{a,b,c,d\}$, because graph $C_4$ is a subgraph of $D_n$, then all of the vertices of every $C_4$ have different colors, as shown in Figure 9.
  Therefore, when we apply any $P_3$ coloring on $D_n$, for any $C_4$ subgraph, its left and right adjacent $C_4$’s have the only possible $P_3$ coloring, as shown in Figure 10.
  Now, this process is continued until a $P_3$-coloring with only four colors $\{a,b,c,d\}$ is completed or produced. We define a $C_4$ to be correctly colored if all its vertices have different colors. Because $n\equiv 0\left(\mathrm{mod}4\right)$, and we have n number of $C_4$s that covers $D_n$, eventually, we will arrive at a situation displayed in Figure 11.
  Since $n\equiv 1\left(\mathrm{mod}4\right)$, from Figure 11, we can easily see that the remaining two $C_4$s cannot be correctly colored with only four given colors. Thus, we have ${\chi }_3\left(D_n\right)\ge 5$, and this shows that we need at least five colors to produce a $P_3$ coloring of $D_n$. For the reverse case, let us define a function g from $V\left(D_n\right)$ to $\{1,2,3,4,5\}$ as follows:

  $$g\left({\alpha }_i\right)=\left\{\begin{array}{cc}i,\hfill & \mathrm{if}1\le i\le 5;\hfill \\ 1,\hfill & \mathrm{if}i\equiv 2mod4,6\le i\le n;\hfill \\ 2,\hfill & \mathrm{if}i\equiv 3mod4,6\le i\le n;\hfill \\ 3,\hfill & \mathrm{if}i\equiv 0mod4,6\le i\le n;\hfill \\ 4,\hfill & \mathrm{if}i\equiv 1mod4,6\le i\le n,\hfill \end{array}\right.$$
  $g\left({\beta }_1\right)=3$, $g\left({\beta }_2\right)=5$,

  $$g\left({\beta }_i\right)=\left\{\begin{array}{cc}i-2,\hfill & \mathrm{if}3\le i\le 7;\hfill \\ 1,\hfill & \mathrm{if}i\equiv 0mod4,8\le i\le n;\hfill \\ 2,\hfill & \mathrm{if}i\equiv 1mod4,8\le i\le n;\hfill \\ 3,\hfill & \mathrm{if}i\equiv 2mod4,8\le i\le n;\hfill \\ 5,\hfill & \mathrm{if}i\equiv 3mod4,8\le i\le n.\hfill \end{array}\right.$$
  Let $Q_2$ be an arbitrary $P_3$ path; then, as before, there will be ten possible $P_3$ paths for any given $i\in \{1,2,\dots n\}$. It is enough to discuss the following possible $P_3$ paths to prove that g is indeed a $P_3$ coloring: ${\alpha }_i{\alpha }_{i+1}{\alpha }_{i+2}$, ${\alpha }_i{\alpha }_{i+1}{\beta }_{i+1}$, ${\alpha }_i,{\beta }_i,{\beta }_{i+1}$, ${\beta }_i{\beta }_{i+1}{\beta }_{i+2}$, ${\beta }_i{\alpha }_i{\alpha }_{i+1}$, ${\beta }_i{\beta }_{i+1}{\alpha }_{i+1}$, ${\alpha }_{i+1}{\alpha }_{i+2}{\beta }_{i+2}$, ${\beta }_{i+1}{\alpha }_{i+1}{\alpha }_{i+2}$, ${\alpha }_{i+2}{\beta }_{i+2}{\beta }_{i+1}$ and the last one is ${\beta }_{i+2}{\beta }_{i+1}{\alpha }_{i+1}$, for all $9\le i\le n-1$.
  It is clear from the above definition that the remaining paths satisfy the $P_3$ coloring, as depicted in Figure 12.
  Now, we will show that g is indeed $P_3$ coloring in four cases, which are discussed below.

  (a). 

  For $i\equiv 0\left(\mathrm{mod}4\right)$ and $9\le i\le n-1$, all possibilities of $Q_2$ are discussed as follows:

  (i) 

  If the path is ${\alpha }_i{\alpha }_{i+1}{\alpha }_{i+2}$, then we have $g\left({\alpha }_i\right)=3,g\left({\alpha }_{i+1}\right)=4,g\left({\alpha }_{i+2}\right)=1$;

  (ii) 

  If the path is ${\alpha }_i{\alpha }_{i+1}{\beta }_{i+1}$, then we have $g\left({\alpha }_i\right)=3,g\left({\alpha }_{i+1}\right)=4,g\left({\beta }_{i+1}\right)=2$;

  (iii) 

  If the path is ${\alpha }_i{b}_i{\beta }_{i+1}$, then we have $g\left({\alpha }_i\right)=3,g\left({\beta }_i\right)=1,g\left({\beta }_{i+1}\right)=2$;

  (iv) 

  If the path is ${\beta }_i{\beta }_{i+1}{\beta }_{i+2}$, then we have $g\left({\beta }_i\right)=1,g\left({\beta }_{i+1}\right)=2,g\left({\beta }_{i+2}\right)=3$;

  (v) 

  If the path is ${\beta }_i{a}_i{\alpha }_{i+1}$, then we have $g\left({\beta }_i\right)=1,g\left({\alpha }_i\right)=3,g\left({\alpha }_{i+1}\right)=4$;

  (vi) 

  If the path is ${\beta }_i{\beta }_{i+1}{\alpha }_{i+1}$, then we have $g\left({\beta }_i\right)=1,g\left({\beta }_{i+1}\right)=2,g\left({\alpha }_{i+1}\right)=4$;

  (vii) 

  If the path is ${\alpha }_{i+1}{\alpha }_{i+2}{\beta }_{i+2}$, then we have $g\left({\alpha }_{i+1}\right)=4,g\left({\alpha }_{i+2}\right)=1$, $g\left({\beta }_{i+2}\right)=3$;

  (viii) 

  If the path is ${\beta }_{i+1}{\alpha }_{i+1}{\alpha }_{i+2}$, then we have $g\left({\beta }_{i+1}\right)=2,g\left({\alpha }_{i+1}\right)=4$, $g\left({\alpha }_{i+2}\right)=1$;

  (ix) 

  If the path is ${\alpha }_{i+2}{\beta }_{i+2}{\beta }_{i+1}$, then we have $g\left({\alpha }_{i+2}\right)=1,g\left({\beta }_{i+2}\right)=3$, $g\left({\beta }_{i+1}\right)=2$;

  (x) 

  If the path is ${\beta }_{i+2}{\beta }_{i+1}{\alpha }_{i+1}$, then we have $g\left({\beta }_{i+2}\right)=3,g\left({\beta }_{i+1}\right)=2$, $g\left({\alpha }_{i+1}\right)=4$.

  (b). 

  For $i\equiv 1\left(\mathrm{mod}4\right)$, all possibilities of $Q_2$ are discussed as follows:

  (i) 

  If the path is ${\alpha }_i{\alpha }_{i+1}{\alpha }_{i+2}$, then we have $g\left({\alpha }_i\right)=4,g\left({\alpha }_{i+1}\right)=5,g\left({\alpha }_{i+2}\right)=2$;

  (ii) 

  If the path is ${\alpha }_i{\alpha }_{i+1}{\beta }_{i+1}$, then we have $g\left({\alpha }_i\right)=4,g\left({\alpha }_{i+1}\right)=5,g\left({\beta }_{i+1}\right)=1$;

  (iii) 

  If the path is ${\alpha }_i{b}_i{\beta }_{i+1}$, then we have $g\left({\alpha }_i\right)=4,g\left({\beta }_i\right)=3,g\left({\beta }_{i+1}\right)=1$;

  (iv) 

  If the path is ${\beta }_i{\beta }_{i+1}{\beta }_{i+2}$, then we have $g\left({\beta }_i\right)=3,g\left({\beta }_{i+1}\right)=1,g\left({\beta }_{i+2}\right)=4$;

  (v) 

  If the path is ${\beta }_i{a}_i{\alpha }_{i+1}$, then we have $g\left({\beta }_i\right)=3,g\left({\alpha }_i\right)=4,g\left({\alpha }_{i+1}\right)=5$;

  (vi) 

  If the path is ${\beta }_i{\beta }_{i+1}{\alpha }_{i+1}$, then we have $g\left({\beta }_i\right)=3,g\left({\beta }_{i+1}\right)=1,g\left({\alpha }_{i+1}\right)=5$;

  (vii) 

  If the path is ${\alpha }_{i+1}{\alpha }_{i+2}{\beta }_{i+2}$, then we have $g\left({\alpha }_{i+1}\right)=5,g\left({\alpha }_{i+2}\right)=2$, $g\left({\beta }_{i+2}\right)=4$;

  (viii) 

  If the path is ${\beta }_{i+1}{\alpha }_{i+1}{\alpha }_{i+2}$, then we have $g\left({\beta }_{i+1}\right)=2,g\left({\alpha }_{i+1}\right)=4$, $g\left({\alpha }_{i+2}\right)=1$;

  (ix) 

  If the path is ${\alpha }_{i+2}{\beta }_{i+2}{\beta }_{i+1}$, then we have $g\left({\alpha }_{i+2}\right)=2,g\left({\beta }_{i+2}\right)=4$, $g\left({\beta }_{i+1}\right)=1$;

  (x) 

  If the path is ${\beta }_{i+2}{\beta }_{i+1}{\alpha }_{i+1}$, then we have $g\left({\beta }_{i+2}\right)=4,g\left({\beta }_{i+1}\right)=1$, $g\left({\alpha }_{i+1}\right)=5$.

  (c). 

  For $i\equiv 2\left(\mathrm{mod}4\right)$, all possibilities of $Q_2$ are discussed as follows:

  (i) 

  If the path is ${\alpha }_i{\alpha }_{i+1}{\alpha }_{i+2}$, then we have $g\left({\alpha }_i\right)=5,g\left({\alpha }_{i+1}\right)=2,g\left({\alpha }_{i+2}\right)=3$;

  (ii) 

  If the path is ${\alpha }_i{\alpha }_{i+1}{\beta }_{i+1}$, then we have $g\left({\alpha }_i\right)=5,g\left({\alpha }_{i+1}\right)=2,g\left({\beta }_{i+1}\right)=4$;

  (iii) 

  If the path is ${\alpha }_i{b}_i{\beta }_{i+1}$, then we have $g\left({\alpha }_i\right)=5,g\left({\beta }_i\right)=1,g\left({\beta }_{i+1}\right)=4$;

  (iv) 

  If the path is ${\beta }_i{\beta }_{i+1}{\beta }_{i+2}$, then we have $g\left({\beta }_i\right)=1,g\left({\beta }_{i+1}\right)=4,g\left({\beta }_{i+2}\right)=5$;

  (v) 

  If the path is ${\beta }_i{a}_i{\alpha }_{i+1}$, then we have $g\left({\beta }_i\right)=1,g\left({\alpha }_i\right)=5,g\left({\alpha }_{i+1}\right)=2$;

  (vi) 

  If the path is ${\beta }_i{\beta }_{i+1}{\alpha }_{i+1}$, then we have $g\left({\beta }_i\right)=1,g\left({\beta }_{i+1}\right)=4,g\left({\alpha }_{i+1}\right)=2$;

  (vii) 

  If the path is ${\alpha }_{i+1}{\alpha }_{i+2}{\beta }_{i+2}$, then we have $g\left({\alpha }_{i+1}\right)=2,g\left({\alpha }_{i+2}\right)=3$, $g\left({\beta }_{i+2}\right)=5$;

  (viii) 

  If the path is ${\beta }_{i+1}{\alpha }_{i+1}{\alpha }_{i+2}$, then we have $g\left({\beta }_{i+1}\right)=2,g\left({\alpha }_{i+1}\right)=4$, $g\left({\alpha }_{i+2}\right)=1$;

  (ix) 

  If the path is ${\alpha }_{i+2}{\beta }_{i+2}{\beta }_{i+1}$, then we have $g\left({\alpha }_{i+2}\right)=3,g\left({\beta }_{i+2}\right)=5$, $g\left({\beta }_{i+1}\right)=4$;

  (x) 

  If the path is ${\beta }_{i+2}{\beta }_{i+1}{\alpha }_{i+1}$, then we have $g\left({\beta }_{i+2}\right)=5,g\left({\beta }_{i+1}\right)=4$, $g\left({\alpha }_{i+1}\right)=2$.

  (d). 

  For $i\equiv 3\left(\mathrm{mod}4\right)$, all possibilities of $Q_2$ are discussed as follows:

  (i) 

  If the path is ${\alpha }_i{\alpha }_{i+1}{\alpha }_{i+2}$, then we have $g\left({\alpha }_i\right)=2,g\left({\alpha }_{i+1}\right)=3,g\left({\alpha }_{i+2}\right)=1$;

  (ii) 

  If the path is ${\alpha }_i{\alpha }_{i+1}{\beta }_{i+1}$, then we have $g\left({\alpha }_i\right)=2,g\left({\alpha }_{i+1}\right)=3,g\left({\beta }_{i+1}\right)=5$;

  (iii) 

  If the path is ${\alpha }_i{b}_i{\beta }_{i+1}$, then we have $g\left({\alpha }_i\right)=2,g\left({\beta }_i\right)=4,g\left({\beta }_{i+1}\right)=5$;

  (iv) 

  If the path is ${\beta }_i{\beta }_{i+1}{\beta }_{i+2}$, then we have $g\left({\beta }_i\right)=4,g\left({\beta }_{i+1}\right)=5,g\left({\beta }_{i+2}\right)=2$;

  (v) 

  If the path is ${\beta }_i{a}_i{\alpha }_{i+1}$, then we have $g\left({\beta }_i\right)=4,g\left({\alpha }_i\right)=2,g\left({\alpha }_{i+1}\right)=3$;

  (vi) 

  If the path is ${\beta }_i{\beta }_{i+1}{\alpha }_{i+1}$, then we have $g\left({\beta }_i\right)=4,g\left({\beta }_{i+1}\right)=5,g\left({\alpha }_{i+1}\right)=3$;

  (vii) 

  If the path is ${\alpha }_{i+1}{\alpha }_{i+2}{\beta }_{i+2}$, then we have $g\left({\alpha }_{i+1}\right)=3,g\left({\alpha }_{i+2}\right)=1$, $g\left({\beta }_{i+2}\right)=2$;

  (viii) 

  If the path is ${\beta }_{i+1}{\alpha }_{i+1}{\alpha }_{i+2}$, then we have $g\left({\beta }_{i+1}\right)=2,g\left({\alpha }_{i+1}\right)=4$, $g\left({\alpha }_{i+2}\right)=1$;

  (ix) 

  If the path is ${\alpha }_{i+2}{\beta }_{i+2}{\beta }_{i+1}$, then we have $g\left({\alpha }_{i+2}\right)=1,g\left({\beta }_{i+2}\right)=2$, $g\left({\beta }_{i+1}\right)=5$;

  (x) 

  If the path is ${\beta }_{i+2}{\beta }_{i+1}{\alpha }_{i+1}$, then we have $g\left({\beta }_{i+2}\right)=2,g\left({\beta }_{i+1}\right)=5$, $g\left({\alpha }_{i+1}\right)=3$.

  Thus, in this case, all of these subcases proved that g is a $P_3$ coloring of $D_n$ for $n\equiv 1\left(\mathrm{mod}4\right)$. Therefore, ${\chi }_{P_3}\left(D_n\right)=5$.
• Case III. Assume that $n\equiv 2\left(\mathrm{mod}4\right)$ and $n\ge 10$. Similarly, as in case II, when we apply any $P_3$ coloring on $D_n$ with only four given colors $\{a,b,c,d\}$, for any $C_4$ subgraph in $D_n$, its left and right adjacent $C_4$’s have the only possible $P_3$ coloring labels, as shown in Figure 13.
  We continue this process to complete (or produce) a $P_3$ coloring with only four colors $a,b,c$ and d. Because $n\equiv 2\left(\mathrm{mod}4\right)$, and we have n number of $C_4$ subgraphs that covers $D_n$, eventually, we will reach the situation displayed in Figure 14.
  Thus, in the case when $n\equiv 2\left(\mathrm{mod}4\right)$, from Figure 14, we can easily see that the remaining three $C_4$s cannot be correctly colored with only four given colors. Thus, we have ${\chi }_3\left(D_n\right)\ge 5$. Therefore, we need at least five colors to produce a $P_3$ coloring of $D_n$. For the reverse case, let us define a function g from $V\left(D_n\right)$ to $\{1,2,3,4,5\}$ as follows:

  $$g\left({\alpha }_i\right)=\left\{\begin{array}{cc}1,\hfill & \mathrm{if}i\equiv 1mod5,1\le i\le 10;\hfill \\ 2,\hfill & \mathrm{if}i\equiv 2mod5,1\le i\le 10;\hfill \\ 3,\hfill & \mathrm{if}i\equiv 3mod5,1\le i\le 10;\hfill \\ 4,\hfill & \mathrm{if}i\equiv 4mod5,1\le i\le 10;\hfill \\ 5,\hfill & \mathrm{if}i\equiv 0mod5,1\le i\le 10;\hfill \\ 1,\hfill & \mathrm{if}i\equiv 3mod4,11\le i\le n;\hfill \\ 2,\hfill & \mathrm{if}i\equiv 0mod4,11\le i\le n;\hfill \\ 3,\hfill & \mathrm{if}i\equiv 1mod4,11\le i\le n;\hfill \\ 4,\hfill & \mathrm{if}i\equiv 2mod4,11\le i\le n.\hfill \end{array}\right.$$
  $g\left({\beta }_1\right)=3$, $g\left({\beta }_2\right)=5$.

  $$g\left({\beta }_i\right)=\left\{\begin{array}{cc}1,\hfill & \mathrm{if}i\equiv 3mod5,3\le i\le 12;\hfill \\ 2,\hfill & \mathrm{if}i\equiv 4mod5,3\le i\le 12;\hfill \\ 3,\hfill & \mathrm{if}i\equiv 0mod5,3\le i\le 12;\hfill \\ 4,\hfill & \mathrm{if}i\equiv 1mod5,3\le i\le 12;\hfill \\ 5,\hfill & \mathrm{if}i\equiv 2mod5,3\le i\le 12;\hfill \\ 1,\hfill & \mathrm{if}i\equiv 1mod4,13\le i\le n;\hfill \\ 2,\hfill & \mathrm{if}i\equiv 2mod4,13\le i\le n;\hfill \\ 3,\hfill & \mathrm{if}i\equiv 3mod4,13\le i\le n;\hfill \\ 5,\hfill & \mathrm{if}i\equiv 0mod4,13\le i\le n.\hfill \end{array}\right.$$
  Let $Q_3$ be an arbitrary $P_3$ path; then, similarly as in case I and case II, it is very easy to see that g is indeed a $P_3$ coloring. Together with the argument at the beginning of this case, this proves that the $P_3$-chromatic number of a prism graph $D_n$ is equal to 5 for $n\equiv 2\left(\mathrm{mod}4\right)$ for all $n\ge 10$.
• Case IV. Assume that $n\equiv 3\left(\mathrm{mod}4\right)$ and $n\ge 15$. Similarly to case II, whenever we apply any $P_3$ coloring on $D_n$ with only four colors $\{a,b,c,d\}$, for any $C_4$ subgraph in $D_n$, its left and right adjacent $C_4$’s have the only possible $P_3$-coloring labels, as shown in Figure 10.

We continue this process to complete (or produce) a $P_3$ coloring with only four colors $a,b,c$, and d. Because $n\equiv 3\left(\mathrm{mod}4\right)$, and we have the n number of $C_4$ subgraphs that covers $D_n$, eventually, we will reach the situation displayed in Figure 11.

Therefore, in the case when $n\equiv 3\left(\mathrm{mod}4\right)$, from Figure 11 and the above argument, we can easily see that the remaining two $C_4$ cannot be correctly colored with only four colors. Thus, we must have ${\chi }_3\left(D_n\right)\ge 5$, that is, we need at least five colors to produce (or obtain) a $P_3$ coloring of $D_n$. For the reverse case, let us define a function g from $V\left(D_n\right)$ to $\{1,2,3,4,5\}$ as follows:

$$g\left({\alpha }_i\right)=\left\{\begin{array}{cc}1,\hfill & \mathrm{if}i\equiv 1mod5,1\le i\le 15;\hfill \\ 2,\hfill & \mathrm{if}i\equiv 2mod5,1\le i\le 15;\hfill \\ 3,\hfill & \mathrm{if}i\equiv 3mod5,1\le i\le 15;\hfill \\ 4,\hfill & \mathrm{if}i\equiv 4mod5,1\le i\le 15;\hfill \\ 5,\hfill & \mathrm{if}i\equiv 0mod5,1\le i\le 15;\hfill \\ 1,\hfill & \mathrm{if}i\equiv 0mod4,16\le i\le n;\hfill \\ 2,\hfill & \mathrm{if}i\equiv 1mod4,16\le i\le n;\hfill \\ 3,\hfill & \mathrm{if}i\equiv 2mod4,16\le i\le n;\hfill \\ 4,\hfill & \mathrm{if}i\equiv 3mod4,16\le i\le n.\hfill \end{array}\right.$$

$g\left({\beta }_1\right)=3$, $g\left({\beta }_2\right)=5$.

$$g\left({\beta }_i\right)=\left\{\begin{array}{cc}1,\hfill & \mathrm{if}i\equiv 3mod5,3\le i\le 17;\hfill \\ 2,\hfill & \mathrm{if}i\equiv 4mod5,3\le i\le 17;\hfill \\ 3,\hfill & \mathrm{if}i\equiv 0mod5,3\le i\le 17;\hfill \\ 4,\hfill & \mathrm{if}i\equiv 1mod5,3\le i\le 17;\hfill \\ 5,\hfill & \mathrm{if}i\equiv 2mod5,3\le i\le 17;\hfill \\ 1,\hfill & \mathrm{if}i\equiv 2mod4,18\le i\le n;\hfill \\ 2,\hfill & \mathrm{if}i\equiv 3mod4,18\le i\le n;\hfill \\ 3,\hfill & \mathrm{if}i\equiv 0mod4,18\le i\le n;\hfill \\ 5,\hfill & \mathrm{if}i\equiv 1mod4,18\le i\le n.\hfill \end{array}\right.$$

Let $Q_4$ be an arbitrary $P_3$ path in $D_n$; then, as in case I and case II, it is very easy to see that g is indeed a $P_3$ coloring. This, combined with the argument at the beginning of this case, proves that the $P_3$-chromatic number of a prism graph $D_n$ is equal to 5 for $n\equiv 3\left(\mathrm{mod}4\right)$, $\forall n\ge 15$.

Thus, the proof of this theorem is completed. □

Theorem 5. 

Let $L_n$ be the ladder graph; then, ${\chi }_3\left(L_n\right)=4$ for all $n\ge 2$.

Proof. 

Let $L_n$ be the ladder graph with $n\ge 2$. Then, by Theorem 1 and Theorem 3, we have ${\chi }_3\left(L_n\right)\ge 4$. To show that ${\chi }_3\left(L_n\right)\le 4$, we will define a labeling g on $V\left(L_n\right)$ to the color set $\{1,2,3,4\}$.

$$g\left({\alpha }_i\right)=\left\{\begin{array}{cc}1,\hfill & \mathrm{if}i\equiv 1mod4,1\le i\le n;\hfill \\ 2,\hfill & \mathrm{if}i\equiv 2mod4,1\le i\le n;\hfill \\ 3,\hfill & \mathrm{if}i\equiv 3mod4,1\le i\le n;\hfill \\ 4,\hfill & \mathrm{if}i\equiv 0mod4,1\le i\le n.\hfill \end{array}\right.$$

$$g\left({\beta }_i\right)=\left\{\begin{array}{cc}3,\hfill & \mathrm{if}i\equiv 1mod4,1\le i\le n;\hfill \\ 4,\hfill & \mathrm{if}i\equiv 2mod4,1\le i\le n;\hfill \\ 1,\hfill & \mathrm{if}i\equiv 3mod4,1\le i\le n;\hfill \\ 2,\hfill & \mathrm{if}i\equiv 0mod4,1\le i\le n.\hfill \end{array}\right.$$

For the reader, this labeling is explained in Figure 15. Let Q be any arbitrary path of $L_n$; then, there are ten possible types of $P_3$ paths in $L_n$, and they are as follows. The paths are ${\alpha }_i{\alpha }_{i+1}{\alpha }_{i+2}$, ${\alpha }_i{\alpha }_{i+1}{\beta }_{i+1}$, ${\alpha }_i{\beta }_i{\beta }_{i+1}$, ${\beta }_i{\beta }_{i+1}{\beta }_{i+2}$, ${\beta }_i{\alpha }_i{\alpha }_{i+1}$, ${\beta }_i{\beta }_{i+1}{\alpha }_{i+1}$, ${\alpha }_{i+1}{\alpha }_{i+2}{\beta }_{i+2}$, ${\beta }_{i+1}{\alpha }_{i+1}{\alpha }_{i+2}$, ${\alpha }_{i+2}{\beta }_{i+2}{\beta }_{i+1}$, and ${\beta }_{i+2}{\beta }_{i+1}{\alpha }_{i+1}$. Then, similarly to the first case of Theorem 4, its clear that f is indeed a $P_3$ coloring. Thus, we achieve the result. □

4. Open Problems and Time Complexity

It is well known that graph coloring and, in particular, vertex coloring is an NP-hard problem. Since our $P_3$ coloring is also a vertex coloring problem, one could speculate that this is also an NP-hard problem. We proved that for some families of graphs, this problem can be solved in polynomial time, which is clear from Theorem 2 to Theorem 5. For future research, we plan to list a few of the open problems concerning this new coloring scheme, which include the following objectives:

• Problem 1: Prove or disprove the conjecture that “The $P_3$ coloring is an NP-hard problem”;
• Problem 2: Discuss all types of time complexity of $P_3$ coloring as an NP-hard problem;
• Problem 3: Find stronger upper and lower bounds of the $P_3$ coloring;
• Problem 4: Find ${\chi }_3\left(Q_n\right)$ for $n\ge 3$.

5. Conclusions

In this article, we introduced a new type of graph coloring scheme, and we called it $P_3$ coloring. A graph having $P_3$ coloring is also a vertex-colorable graph (in a normal sense). We proved that when a graph has a vertex that is adjacent to all other vertices of the graph, its $P_3$-chromatic number is the cardinality of the vertices of the graph. Then, we computed the $P_3$ chromatic number of some well-known families of graphs. To this end, we computed the $P_3$-chromatic number of path, cycle, prism, and ladder graphs. It is clear from the above discussion and results that the $P_3$-chromatic number of a graph is greater than or equal to its chromatic number. Graph coloring always raises strong interest among mathematicians and other related researchers. Therefore, any new and novel coloring technique is always followed by numerous graph-coloring studies in the literature. We gave an example of a challenge that can be countered only by using $P_3$ coloring. This also gives us the reasons for why this type of coloring should exist. We presented some future plans and open problems to further advance in this topic and extend its application.