d-Distance Coloring of Generalized Petersen Graphs P(n, k)

Ramy Shaheen, Ziad Kanaya, Samar Jakhlab

Department of Mathematics, Faculty of Science, Tishreen University, Lattakia, Syria.

DOI: 10.4236/ojdm.2017.74017                

Abstract

A coloring of G is d-distance if any two vertices at distance at most d from each other get different colors. The minimum number of colors in d-distance colorings of G is its d-distance chromatic number, denoted by χ_d(G). In this paper, we give the exact value of χ_d(G) (d = 1, 2), for some types of generalized Petersen graphs P(n, k) where k = 1, 2, 3 and arbitrary n.

Keywords

Distance Coloring, Generalized Petersen Graphs

1. Introduction

Let G = (V, E) be simple graph. A vertex k-coloring of G is a mapping from V(G) to the set $\left\{1,2,\cdots ,k\right\}$ such that any two adjacent vertices are mapped to different integers. The smallest integer k for which a k-coloring exists is called the chromatic number of G, denoted by c(G). The d-distance between two distinct vertices u and v, d(u, v) is the number of edges of the shortest path joining them. The d-distance k-coloring, also called distance (d, k)-coloring, is a k-coloring of the graph G, that is, any two vertices within distance d in G receive different colors. The d-distance chromatic number of G is exactly the chromatic number of G under the d-distance condition, denoted by c_d(G). For a simple graph G, the dth power of G, (G^d of G) is defined such that $V\left(G^d\right)=V\left(G\right)$ and two vertices u and v are adjacent in G^d if and only if the distance between u and v in G is at most d. Clearly, the following inequality is holds:

$\chi \left(G\right)={\chi }_1\left(G\right)\le \chi \left(G^2\right)={\chi }_2\left(G\right)\le \chi \left(G^d\right)={\chi }_d\left(G\right)\text{for}d\ge 2.$

The theory of plane graph coloring has a long history, extending back to the middle of the 19^thcentury. In 1969, Florica Kramer and Horst Kramer [1] [2] defined the chromatic number ${\chi }_d\left(G\right)$ relative to distance d of a graph G(V, E) to be the minimum number of colors which are sufficient for coloring the vertices of G in such a way that any two vertices of G of distance not greater than d have distinct colors. In 1977, Wegner [3] , studied the problem of distance coloring of planar graphs. Alon and Mohar [4] considered the maximum possible chromatic number of G², as G ranges over all graphs with maximum degree d and girth g. Bonamy et al. [5] , studied the 2-distance coloring of sparse graphs. They proved that every graph with maximum degree Δ at least 4 and maximum average degree less that 7/3 admits a 2-distance (Δ + 1)-coloring. Okamoto and Zhang [6] , considered the 2-distance chromatic number of graphs when deleted an edge or a vertex. In [7] , Jacko gave the exact value of c_d(G) of hexagonal lattice graph when d is odd and some value when d is even. Borodin and Ivanova [8] , proved that every planar graph with g ≥ 6 and ∆ ≥ 18 is (∆ + 2)-colorable. Dantas et al. [9] , studied the total coloring of generalized Petersen graphs and shown that “almost all” generalized Petersen graphs have a total chromatic number 4. Miao and Fan, [10] , gave an upper bound of the chromatic number c_d(G). Many papers have been devoted to it during the last decade, see for example [11] [12] [13] [14] [15] .

In this paper, all graphs are finite, simple and undirected. For a graph G, we denote by V(G), E(G), d(u,v), ∆(G), diam(G), G^d and ${\chi }_d\left(G\right)$ its vertex set, edge set, the distance between u and v which is the length of shortest path connecting them, the maximum vertex degree, the diameter of G, the power of G and d-distance coloring of G.

Theorem 1.1. [1] : For a graph $G=\left(V,E\right)$ we have ${\chi }_d\left(G\right)=d+1$ if and only if the graph G is satisfying one of the following conditions:

1) $\left|V\right|=d+1$ .

2) G is a path of length greater than d.

3) G is a cycle of length a multiple of (d + 1). □

Theorem 1.2. [10] : When $\Delta =2$ , there exist only two connected graphs of order n:

The path $P_n$ and the cycle $C_n$ :

1). ${\chi }_d\left(P_n\right)=\min \left\{n,d+1\right\}$ .

2). ${\chi }_d\left(C_n\right)=\{\begin{array}{l}d+1:n\equiv 0\left(\mathrm{mod}\left(d+1\right)\right),\\ \min \left\{i+1\ge d+2:n\mathrm{mod}i\le \frac{n}{i}\right\}.\end{array}$

Theorem 1.3. [10] : Let G be a graph. Then

${\chi }_d\left(G\right)\le \Delta \frac{{\left(\Delta -1\right)}^d-1}{\Delta -2}+1.$

□

Lemma 1.1. [6] : Let G be a nontrivial graph and d a positive integer.

1) If H a subgraph of G, then ${\chi }_d\left(H\right)\le {\chi }_d\left(G\right)$ .

2) ${\chi }_d\left(G\right)$ equals the order of G if and only if G is connected and $\text{diam}\left(G\right)\le d$ . □

Definition 1.1. [9] : For integers n and k with $2\le 2k<n$ . The Generalized Petersen Graph $P\left(n,k\right)$ has vertices and respectively Edges given by:

$V\left(P\left(n,k\right)\right)=\left\{a_i,b_i:1\le i\le n,1\le k\le \left[\frac{n-1}{2}\right]\right\}$ ,

$E\left(P\left(n,k\right)\right)=\left\{a_i{a}_{i+1},a_i{b}_i,b_i{b}_{i+k}:1\le i\le n\right\}$

□

We will call $A\left(n,k\right)$ (respectively $B\left(n,k\right)$ ) the outer (respectively inner) subgraph of $P\left(n,k\right)$ . Note that we take the skip $k\le \lfloor \frac{n-1}{2}\rfloor$ , because of the obvious isomorphism $P\left(n,k\right)\cong P\left(n,n-k\right)$ .

2. Main Results

Our main results here are to establish the exact chromatic number ${\chi }_d\left(P\left(n,k\right)\right)$ (d = 1, 2) for k = 1, 2, 3 and arbitrary n.

Theorem 2.1. ${\chi }_1\left(P\left(n,1\right)\right)=\{\begin{array}{l}2:n\text{even},\\ 3:n\text{odd}.\end{array}$

Proof. Let $G=P\left(n,1\right)$ , observe from Definition 1.1, that Generalized Petersen Graphs composed of one outer cycle and several inner cycles dependent on k. So, when k = 1 there is one inner cycle, then G composed of two cycles of size n. There are two cases:

Case 1: n is even, immediately from Theorem 1.1 we have ${\chi }_1\left(C_n\right)=2$ (because d = 1) then

${\chi }_1\left(G\right)\ge 2$ (1)

We define a function f with colors in the set {1, 2} for a_i and b_i as follows:

$f\left(a_i\right)=\{\begin{array}{l}1:i\text{odd},\\ 2:i\text{even}.\end{array}$ , $f\left(b_i\right)=\{\begin{array}{l}2:i\text{odd},\\ 1:i\text{even}.\end{array}$

Then

${\chi }_1\left(G\right)\le 2$ (2)

By (1) and (2) we get ${\chi }_1\left(G\right)=2$ .

Case 2: n is odd, from Theorem 1.2, we have ${\chi }_1\left(C_n\right)=3$ . Then

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

We define a function f with colors in the set {1, 2, 3} for a_i and b_i as follows:

$f\left(a_i\right)=\{\begin{array}{l}1:i\text{odd}\text{and}i<n,\\ 2:i\text{even},\\ 3:i=n.\end{array},f\left(b_i\right)=\{\begin{array}{l}2:i\text{odd}\text{and}i<n,\\ 1:i\text{even}\text{and}i=n\text{such}\text{that}i\ne n-1,\\ 3:i=n-1.\end{array}$

So,

${\chi }_1\left(G\right)\le 3$ . (4)

From (3) and (4), gets ${\chi }_1\left(G\right)=3$ . As example see Figure 1.

Theorem 2.2: ${\chi }_2\left(P\left(n,1\right)\right)=\{\begin{array}{l}4:n\equiv 0\left(\mathrm{mod}4\right),\\ 6:n=3,6,\\ 5:\text{otherwise}.\end{array}$

Proof. Let $G=P\left(n,1\right)$ . We have $C_4$ is an induced subgraph of G and from Theorem 1.2, gets ${\chi }_2\left(C_4\right)=4$ . So,

${\chi }_2\left(G\right)\ge 4$ (5)

We define a function f with colors in the set $\left\{\text{1},\text{2},\text{3},\text{4}\right\}$ for a_i and b_i as follows:

$f\left(a_1\right)=1$ , $f\left(b_1\right)=3$ , $f\left(a_2\right)=2$ , $f\left(b_2\right)=4$ .

By follow-up the coloring to the right, for $a_3$ there is only a single color as $f\left(a_3\right)=3$ .

So, for each vertex there is only a single color:

$f\left(b_3\right)=1$ , $f\left(a_4\right)=4$ , $f\left(b_4\right)=2$ , $f\left(a_5\right)=1$ ,

$f\left(b_5\right)=3$ , $f\left(a_6\right)=2$ , $f\left(b_6\right)=4$ .

Observe that we have a repeat of the same order of the colors for each 4-inner (4-outer) vertices. Consider G with $n\ge 4$ . Assume that $n=4q+r$ : $0\le r<4$ for each $j\in \left\{0,4,\cdots ,4\left(q-1\right)\right\}$ we define a subset $S_j$ of V(G) by $S_j=\left\{a_i,a_{i+1},a_{i+2},a_{i+3},b_i,b_{i+1},b_{i+2},b_{i+3}\right\}$ then there is a function f with colors in the set $\left\{\text{1},\text{2},\text{3},\text{4}\right\}$ define as follows:

$f\left(a_i\right)=\{\begin{array}{l}1:i\equiv 1\left(\mathrm{mod}4\right),\\ 2:i\equiv 2\left(\mathrm{mod}4\right),\\ 3:i\equiv 3\left(\mathrm{mod}4\right),\\ 4:i\equiv 0\left(\mathrm{mod}4\right).\end{array}$ , $f\left(b_i\right)=\{\begin{array}{l}3:i\equiv 1\left(\mathrm{mod}4\right),\\ 4:i\equiv 2\left(\mathrm{mod}4\right),\\ 1:i\equiv 3\left(\mathrm{mod}4\right),\\ 2:i\equiv 0\left(\mathrm{mod}4\right).\end{array}$

We have four cases according to the value of n modulo 4:

Case 1: r = 0. Then $V\left(G\right)={\displaystyle {\cup }_{j=0}^{4\left(q-1\right)}{S}_j}$ . By function f is

${\chi }_2\left(G\right)\le 4$ (6)

From (5) and (6), we get ${\chi }_2\left(G\right)=4:n\equiv 0\left(\mathrm{mod}4\right)$ .

Figure 1. ${\chi }_1\left(P\left(7,1\right)\right)=3$ .

Case 2: r = 1. There are two leftover vertices in $V\left(G\right)-{\displaystyle \cup S_j}=\left\{a_n,b_n\right\}$ . By function f we have $f\left(a_n\right)=1$ , $f\left(b_n\right)=3$ which is a contradiction with $a_1$ and $b_1$ . Moreover $d\left(a_n,b_n\right)=1$ . So, each of $a_n$ and $b_n$ needs deferent color then ${\chi }_2\left(G\right)>4$ . We define $f_1=f\backslash \left\{a_n,a_{n-1},a_{n-2},b_n\right\}\cup f_2$ , where $f_2$ is a function with colors in the set {3, 4, 5} define as follows:

$f_2\left(v\right)=\{\begin{array}{l}4:v=a_n,\\ 3:v=a_{n-1},\\ 5:v=a_{n-2},b_{\begin{array}{c}n\end{array}}.\end{array}$

Then we get ${\chi }_2\left(G\right)=5$ = when $n\equiv 1\left(\mathrm{mod}4\right)$ .

Case 3: For r = 2, we have two subcases:

Case 3.1: r = 2 and n > 6, a similar argument, there is a contradiction for $a_n$ , $b_n$ , $a_{n-1}$ , $b_{n-1}$ . Then, ${\chi }_2\left(G\right)>4$ . We define

$f_1=f\backslash \left\{a_n,b_n,a_{n-1},b_{n-1},a_{n-2},b_{n-2},a_{n-3},a_{n-4},b_1,b_2\right\}\cup f_2.$

$f_2$ is a function with colors in the set $\left\{\text{2},\text{3},\text{4},\text{5}\right\}$ define as follows:

$f_2\left(v\right)=\{\begin{array}{l}2:v=a_{n-3},b_{n-1},\\ 3:v=a_{n-2},b_n,\\ 4:v=a_{n-1},b_1,\\ 5:v=a_n,a_{n-4},b_{n-2},b_2.\end{array}$

Then we get ${\chi }_2\left(G\right)=5$ when $n\equiv 2\left(\mathrm{mod}4\right)$ , see Figure 2.

Case 3.2: r = 2 and n = 6. There are two cycles of order 6 and know that ${\chi }_2\left(C_6\right)=3$ . Without loss of generality, assuming that $f\left(a_1\right)=1$ . Then the vertices a₂, a₃, a₅, a₆, b₁, b₂, b₆, can’t take the color 1. Moreover, at most one of a₄, b₃, b₄, b₅ can be coloring by 1. This implies that each color has only two vertices from $P\left(6,1\right)$ . So, needs 6 colors for 12 vertices. Furthermore, ${\chi }_2\left(P\left(6,1\right)\right)=6$ .

Case 4: For r = 3, there are two subcases:

Case 4.1: n ≥ 7. For a function coloring f there is a contradiction in $a_n$ and $b_n$ . Then ${\chi }_2\left(G\right)>4$ . We define

Figure 2. ${\chi }_2\left(P\left(10,1\right)\right)=5$ .

$f_1=f\backslash \left\{a_n,b_n,a_{n-1},b_{n-2}\right\}\cup f_2$

where $f_2$ is a function with colors in the set $\left\{\text{2},\text{3},\text{5}\right\}$ define as follows:

$f_2\left(v\right)=\{\begin{array}{l}2:v=b_n,\\ 3:v=a_{n-1},\\ 5:v=a_n,b_{n-2}.\end{array}$

Then, ${\chi }_2\left(G\right)=5$ when $n\equiv 3\left(\mathrm{mod}4\right)$ .

Case 4.2: n = 3. Then, $\text{diam}\left(P\left(\text{6},\text{1}\right)\right)=2$ . By Lemma 1.1, we get ${\chi }_2\left(G\right)=6$ . □

Theorem 2.3: ${\chi }_1\left(P\left(n,2\right)\right)=3$ .

Proof: Let $G=P\left(n,2\right)$ . We have $C_5$ is an induced subgraph of G. Then by Theorem 1.2, is ${\chi }_1\left(C_5\right)=3$ . So,

${\chi }_1\left(G\right)\ge 3$ (7)

We define a function f as follows:

$f\left(a_i\right)=\{\begin{array}{l}1:i\equiv 1\left(\mathrm{mod}3\right),\\ 2:i\equiv 2\left(\mathrm{mod}3\right),\\ 3:i\equiv 0\left(\mathrm{mod}3\right).\end{array}$ , $f\left(b_i\right)=\{\begin{array}{l}2:i\equiv 1\left(\mathrm{mod}3\right),\\ 3:i\equiv 2\left(\mathrm{mod}3\right),\\ 1:i\equiv 0\left(\mathrm{mod}3\right).\end{array}$

We have three cases according to the value of n modulo 3:

Case 1: r = 0. By definition f we have

${\chi }_1\left(G\right)\le 3$ (8)

By (7) together with (8), gets ${\chi }_1\left(G\right)=3$ when $n\equiv 0\left(\mathrm{mod}3\right)$ .

Case 2: r = 1. Then there is a contradiction for $a_n$ . We define

$f_1=f\backslash \left\{a_1\right\}\cup f_2$

where $f_2\left(a_1\right)=3$ . This implies that ${\chi }_1\left(G\right)=3$ when $n\equiv 1\left(\mathrm{mod}3\right)$ .

Case 3: r = 2. There is a problem with colors the vertices $\left\{b_n,b_{n-1}\right\}$ .

We define $f_1=f\backslash \left\{a_n,b_n,a_{n-1},b_{n-1}\right\}\cup f_2$ , where $f_2$ is a function with colors in the set $\left\{\text{1},\text{2},\text{3}\right\}$ define as follows:

$f_2\left(v\right)=\{\begin{array}{l}1:v=b_{n-1},\\ 3:v=a_n,\\ 2:v=a_{n-1},b_n.\end{array}$

By the last result together with (7), we get ${\chi }_2\left(G\right)=3$ when $n\equiv 2\left(\mathrm{mod}3\right)$ . □

Theorem 2.4: ${\chi }_2\left(P\left(n,2\right)\right)=\{\begin{array}{l}5:n\equiv 0\left(\mathrm{mod}10\right),\\ 10:n=5,\\ 6:\text{otherwise}.\end{array}$

Proof: Let $G=P\left(n,2\right)$ . G including $C_5$ as an induced subgraph. We have $\text{diam}\left(C_5\right)=2$ . Then by Lemma 1.1, we get ${\chi }_2\left(C_5\right)=5$ . Furthermore

${\chi }_2\left(G\right)\ge 5.$ (9)

We define a function f with colors in the set $\left\{\text{1},\text{2},\text{3},\text{4},\text{5}\right\}$ for $a_i$ and $b_i$ as follows:

$f\left(a_1\right)=2$ , $f\left(a_2\right)=2$ , $f\left(a_3\right)=3$ , $f\left(b_1\right)=4$ , $f\left(b_3\right)=5$

Then for $b_2$ there are two cases:

Case a: $f\left(b_2\right)=4$ . (By coloring to the right). So, $a_4$ has only a single color as $f\left(a_4\right)=1$ and $f\left(b_4\right)=5$ . Follow-up coloring inner (outer) vertices each vertex will have only a single color as follows:

$f\left(b_5\right)=2$ , $f\left(a_5\right)=4$ , $f\left(b_6\right)=2$ , $f\left(a_6\right)=3$ , $f\left(b_7\right)=1$ , $f\left(a_7\right)=5$ ,

$f\left(b_8\right)=1$ , $f\left(a_8\right)=4$ , $f\left(b_9\right)=3$ , $f\left(a_9\right)=2$ , $f\left(b_{10}\right)=3$ , $f\left(a_{10}\right)=5$

By continue we will have a repeat of the same order of the colors for each 10-inner (10-outer) vertices.

Case b: $f\left(b_2\right)=5$ . By coloring to the left. So, we back to consider the Case 1.

We will consider G with $n\ge 10$ . Assume that $n=10q+r$ : $0\le r<10$ . Now, for each $j\in \left\{0,10,\cdots ,10\left(q-1\right)\right\}$ we define a subset $S_j$ of V(G) by

$S_j=\left\{a_j,a_{j+1},\cdots ,a_{j+9},b_j,b_{j+1},\cdots ,b_{j+9}\right\}$

Then there is a function f define as follows:

$f\left(a_i\right)=\{\begin{array}{l}1:i\equiv 1,4\left(\mathrm{mod}10\right),\\ 2:i\equiv 2,9\left(\mathrm{mod}10\right),\\ 3:i\equiv 3,6\left(\mathrm{mod}10\right),\\ 4:i\equiv 5,8\left(\mathrm{mod}10\right),\\ 5:i\equiv 7,0\left(\mathrm{mod}10\right).\end{array}$ , $f\left(b_i\right)=\{\begin{array}{l}4:i\equiv 12\left(\mathrm{mod}10\right),\\ 5:i\equiv 3,4\left(\mathrm{mod}10\right),\\ 2:i\equiv 5,6\left(\mathrm{mod}10\right),\\ 1:i\equiv 7,8\left(\mathrm{mod}10\right),\\ 3:i\equiv 0,9\left(\mathrm{mod}10\right).\end{array}$

We have ten cases according to the value of n modulo 10:

Case 1: r = 0. Then $V\left(G\right)={\displaystyle {\cup }_{j=0}^{10\left(q-1\right)}{S}_j}$ . Moreover, by define f we have

${\chi }_2\left(G\right)\le 5$ (10)

From (9) and (10) we get ${\chi }_2\left(G\right)=5$ when $n\equiv 0\left(\mathrm{mod}10\right)$ .

Case 2: r = 1. There are two leftover vertices in $V\left(G\right)-{\displaystyle \cup S_j}=\left\{a_n,b_n\right\}$ . By function f, $f\left(a_n\right)=1$ , $f\left(b_n\right)=4$ which is a contradiction with $a_1$ and $b_1$ , and $d\left(a_n,b_n\right)=1$ . So each of $a_n$ and $b_n$ needs deferent color then ${\chi }_2\left(G\right)>5$ . We define

$f_1=f\backslash \left\{a_n,b_n,a_{n-1},a_{n-2},a_{n-3}\right\}\cup f_2$

where $f_2$ is a function with colors in the set $\left\{\text{2},\text{4},\text{5},\text{6}\right\}$ define as follows:

$f_2\left(v\right)=\{\begin{array}{l}2:v=a_{n-1},\\ 4:v=a_{n-2},\\ 5:v=a_n,\\ 6:v=b_n,a_{n-3}.\end{array}$

Then we get ${\chi }_2\left(G\right)=6$ when $n\equiv 1\left(\mathrm{mod}10\right)$ .

Case 3: r = 2. There are four leftover vertices in $V\left(G\right)-{\displaystyle \cup S_j}=\left\{a_n,b_n,a_{n-1},b_{n-1}\right\}$ , which are a contradiction with $\left\{a_1,a_2,b_1,b_2\right\}$ . This implies that ${\chi }_2\left(G\right)>5$ .

Let

$f_1=f\backslash \left\{b_n,b_{n-1},a_1,a_2,a_3,a_4,a_6\right\}\cup f_2$

where $f_2$ is a function with colors in the set $\left\{\text{1},\text{3},\text{6}\right\}$ define as follows:

$f_2\left(v\right)=\{\begin{array}{l}1:v=a_2,\\ 3:v=a_1,a_4,\\ 6:v=a_3,a_6,b_n,b_{n-1}.\end{array}$

Then ${\chi }_2\left(G\right)=6$ when $n\equiv 2\left(\mathrm{mod}10\right)$ . See Figure 3.

Case 4: r = 3. By same argument there is a contradiction for $b_n,b_{n-1},b_{n-2}$ . Which implies that ${\chi }_2\left(G\right)>5$ . So, we define

$f_1=f\backslash \left\{b_n,b_{n-1},b_{n-2},a_{n-3},a_{n-5}\right\}\cup f_2$

where that $f_2$ is a function with colors in the set $\left\{\text{4},\text{5},\text{6}\right\}$ define as follows:

$f_2\left(v\right)=\{\begin{array}{l}4:v=a_{n-3},\\ 5:v=b_{n-2},\\ 6:v=b_n,b_{n-1},a_{n-5}.\end{array}$

Then we get ${\chi }_2\left(G\right)=6$ when $n\equiv 3\left(\mathrm{mod}10\right)$ .

Case 5: r = 4. There is a contradiction for $b_n,b_{n-1},b_{n-2},b_{n-3},a_n$ . We define

$f_1=f\backslash \left\{a_1,a_n,a_{n-3},b_n,b_{n-1},b_{n-2},b_{n-3}\right\}\cup f_2$

where $f_2$ is a function with colors in the set $\left\{1,4,5,6\right\}$ define as follows:

$f_2\left(v\right)=\{\begin{array}{l}1:v=b_n,b_{n-1},\\ 4:v=a_{n-3},\\ 5:v=a_n,\\ 6:v=a_1,b_{n-2},b_{n-3}.\end{array}$

We get ${\chi }_2\left(G\right)=6$ when $n\equiv 4\left(\mathrm{mod}10\right)$ .

Case 6: When r = 5 we have two subcases:

Case 6.1: r = 5 and $n>5$ . The contradiction is for $b_n,b_{n-1},b_{n-3},a_{n-1},a_n$ . We will need at least three new deferent colors for them, then ${\chi }_2\left(G\right)>5$ . We define

Figure 3. ${\chi }_2\left(P\left(12,2\right)\right)=6$ .

$f_1=f\backslash \left\{a_n,b_n,a_{n-1},b_{n-1},a_{n-2},b_{n-3},a_{n-4},b_{n-4},a_{n-5},b_{n-6},b_{n-7},a_2,a_3\right\}\cup f_2$

where $f_2$ is a function with colors in the set $\left\{1,2,3,4,5,6\right\}$ define as follows:

$f_2\left(v\right)=\{\begin{array}{l}1:v=a_{n-2},a_{n-5},\\ 2:v=a_n,\\ 3:v=a_{n-1},a_2,b_{n-4},\\ 4:v=a_{n-4},\\ 5:v=b_{n-3},\\ 6:v=a_3,b_n,b_{n-1},b_{n-6},b_{n-7}.\end{array}$

Then ${\chi }_2\left(G\right)=6$ when $n\equiv 5\left(\mathrm{mod}10\right)$ . See Figure 4.

Case 6. 2: r = 5 and n = 5. We have diam(G) = 2. So, Lemma 1.1, gets ${\chi }_2\left(G\right)=10$ .

Case 7: r = 6. A contradiction for $b_n$ , $a_{n-1}$ . We define $f_1=f\backslash \left\{b_1,b_n\right\}\cup f_2$ and $f_2$ is a function with color 6. So, $f_2\left(b_1\right)=f_2\left(b_n\right)=6$ , gets ${\chi }_2\left(G\right)=6$ when $n\equiv 6\left(\mathrm{mod}10\right)$ .

Notice when n = 6 we have the same argument but $q=0$ , so the vertices will take the sequence of colors for (outer, inner)vertices as follows (1, 2, 3, 1, 2, 3, 4, 4, 5, 5, 6, 6).

Case 8: r = 7. A contradiction is only for $b_n$ . Let $f_1=f\backslash \left\{b_n\right\}\cup f_2$ . Where $f_2\left(b_n\right)=6$ . Moreover, ${\chi }_2\left(G\right)=6$ when $n\equiv 7\left(\mathrm{mod}10\right)$ . Also when n = 7 we get ${\chi }_2\left(G\right)=6$ by the same condition with sequence of colors (outer, inner) vertices as following (1, 2, 3, 1, 4, 3, 5, 6, 4, 5, 5, 2, 2, 6).

Case 9: r = 8. A contradiction is for $b_{n-1}$ , $b_n$ , $a_n$ , then ${\chi }_2\left(G\right)>5$ . We define $f_1=f\backslash \left\{a_n,b_n,b_{n-1},a_{n-2},a_{n-3}\right\}\cup f_2$ with $f_2$ is a function with colors in the set $\left\{\text{3},\text{4},\text{6}\right\}$ define as follows:

$f_2\left(v\right)=\{\begin{array}{l}3:v=b_n,b_{n-1},\\ 4:v=a_{n-2},\\ 6:v=a_n,a_{n-3}.\end{array}$

Figure 4. ${\chi }_2\left(P\left(15,2\right)\right)=6$ .

And so, gets ${\chi }_2\left(G\right)=6$ when $n\equiv 8\left(\mathrm{mod}10\right)$ .

Also notice when n = 8 we have the same argument but $q=0$ , so the vertices will take the sequence of colors for (outer, inner) vertices as follows (1, 2, 3, 1, 6, 4, 5, 6, 4, 4, 5, 5, 2, 2, 3, 3).

Case 10: r = 9. There is a contradiction for $b_{n-1}$ , $a_{n-1}$ , $a_n$ then ${\chi }_2\left(G\right)>5$ . Let us define $f_1=f\backslash \left\{a_n,b_n,a_{n-1},b_{n-1},a_{n-2},a_{n-4}\right\}\cup f_2$ , with $f_2$ is a function with colors in the set $\left\{\text{3},\text{4},\text{5},\text{6}\right\}$ define as follows:

$f_2\left(v\right)=\{\begin{array}{l}3:v=a_n,\\ 4:v=a_{n-2},\\ 5:v=a_{n-1},\\ 6:v=b_n,b_{n-1},a_{n-4}.\end{array}$

Furthermore, ${\chi }_2\left(G\right)=6$ when $n\equiv 9\left(\mathrm{mod}10\right)$ .

As before when n = 9 we get ${\chi }_2\left(G\right)=6$ , by the same condition with sequence of colors (outer, inner) vertices as follows (1, 2, 3, 1, 6, 3, 4, 5, 3, 4, 4, 5, 5, 2, 2, 1, 6, 6).

Finally, we conclude that:

${\chi }_2\left(P\left(n,2\right)\right)=\{\begin{array}{l}5:n\equiv 0\left(\mathrm{mod}10\right),\\ 10:n=5,\\ 6:\text{otherwise}.\end{array}$

Theorem 2.5: ${\chi }_1\left(P\left(n,3\right)\right)=\{\begin{array}{l}2:n\equiv 0\left(\mathrm{mod}2\right),\\ 3:n\equiv 1\left(\mathrm{mod}2\right).\end{array}$

Proof. Let $G=P\left(n,3\right)$ . There are two cases:

Case 1: $n\equiv 0\left(\mathrm{mod}2\right)$ . From Theorem 1.2, we have ${\chi }_1\left(C_n\right)=2$ . Then

${\chi }_1\left(G\right)\ge 2$ (11)

We define a function f with colors in the set {1, 2} for $a_i$ and $b_i$ ( $1\le i\le n$ ),

$f\left(a_i\right)=\{\begin{array}{l}1:i\text{odd},\\ 2:i\text{even}.\end{array}$ , $f\left(b_i\right)=\{\begin{array}{l}2:i\text{odd},\\ 1:i\text{even}.\end{array}$

Then

${\chi }_1\left(G\right)\le 2$ (12)

From (11) and (12), gets ${\chi }_1\left(G\right)=2$ .

Case 2: $n\equiv 1\left(\mathrm{mod}2\right)$ . From Theorem 1.2, we have ${\chi }_1\left(C_n\right)=3$ . Moreover,

${\chi }_1\left(G\right)\ge 3$ (13)

Let $f:V\left(G\right)\to \left\{1,2,3\right\}$ for $a_i$ and $b_i$ , where

$f\left(a_i\right)=\{\begin{array}{l}1:i\text{odd},i=n-1\text{such}\text{that}i\ne n,n-2,\\ 2:i\text{even},i=n,n-2\text{such}\text{that}i\ne n-1,n-3,\\ 3:i=n-3.\end{array}$

$f\left(b_i\right)=\{\begin{array}{l}1:i\text{even},i<n-2,\\ 2:i\text{odd},i<n-2,\\ 3:i=n,n-1,n-2.\end{array}$

Then

${\chi }_1\left(G\right)\le 3$ . (14)

From (13) and (14) is ${\chi }_1\left(G\right)=3$ . □

Theorem 2.6: ${\chi }_2\left(P\left(n,3\right)\right)=\{\begin{array}{l}4:n\equiv 0\left(\mathrm{mod}4\right),\\ 6:n=7\text{or}2\left(\mathrm{mod}4\right),\\ 5:\text{otherwise}.\end{array}$

Proof. Let $G=P\left(n,3\right)$ . $K\left(1,3\right)$ is an induced subgraph of G and ${\chi }_2\left(K\left(1,3\right)\right)=4$ . This implies that

${\chi }_2\left(G\right)\ge 4$ . (15)

Without loss of generality, we define a function f as follows: $f\left(a_1\right)=1$ , $f\left(a_2\right)=2$ , $f\left(a_3\right)=3$ , $f\left(b_2\right)=4$ . By follow-up the coloring to the right, for $b_1$ there are two cases $f\left(b_1\right)=4$ or $f\left(b_1\right)=3$ .

Case 1: $f\left(b_1\right)=4$ . Then, there are two cases for $b_3$ , $f\left(b_3\right)=4$ or $f\left(b_3\right)=1$ . So, if $f\left(b_3\right)=4$ then absolutely $f\left(a_4\right)=1$ and $f\left(b_1\right)=3$ . For coloring $a_5$ we need another color because it has the four colors as neighbors. If $f\left(b_3\right)=1$ , then $f\left(a_4\right)=1$ and $f\left(b_4\right)=2$ . Furthermore, for coloring $a_5$ we need another color. So to avoiding the fifth color we have to take the second case.

Case 2: $f\left(b_1\right)=3$ . There are two cases for $b_3$ , $f\left(b_3\right)=4$ or $f\left(b_3\right)=1$ , we have two subcases:

Case 2.1: $f\left(b_3\right)=4$ . Absolutely $f\left(a_4\right)=1$ and $f\left(b_4\right)=4$ or $f\left(b_4\right)=2$ . If we take $f\left(b_4\right)=4$ then $f\left(a_5\right)=2$ , $f\left(b_5\right)=3$ , but we need another color for $a_6$ . Also if we take $f\left(b_4\right)=2$ then we need new color for $a_5$ .

Case 2.2: $f\left(b_3\right)=1$ . For each vertex there is only a single color: $f\left(a_4\right)=4$ , $f\left(b_4\right)=2$ , $f\left(a_5\right)=1$ , $f\left(b_5\right)=3$ , $f\left(a_6\right)=2$ , $f\left(b_6\right)=4$ . Observe that, we have a repeat of the same order of the colors for each (4-outer) and (4-inner) vertices as respectively for colors $\left\{\text{1},\text{2},\text{3},\text{4}\right\}$ and $\left\{\text{3},\text{4},\text{1},\text{2}\right\}$ . Consider G with $n\ge 4$ . Assume that $n=4q+r$ : $0\le r<4$ for each $j\in \left\{0,4,\cdots ,4\left(q-1\right)\right\}$ , we define a subset $S_j$ of V(G) by $S_j=\left\{a_i,a_{i+1},a_{i+2},a_{i+3},b_i,b_{i+1},b_{i+2},b_{i+3}\right\}$ then there is a function f define as follows:

$f\left(a_i\right)=\{\begin{array}{l}1:i\equiv 1\left(\mathrm{mod}4\right),\\ 2:i\equiv 2\left(\mathrm{mod}4\right),\\ 3:i\equiv 3\left(\mathrm{mod}4\right),\\ 4:i\equiv 0\left(\mathrm{mod}4\right).\end{array}$ , $f\left(b_i\right)=\{\begin{array}{l}3:i\equiv 1\left(\mathrm{mod}4\right),\\ 4:i\equiv 2\left(\mathrm{mod}4\right),\\ 1:i\equiv 3\left(\mathrm{mod}4\right),\\ 2:i\equiv 0\left(\mathrm{mod}4\right).\end{array}$

We have four cases according to the value of n modulo 4:

Case 2.2.1: r = 0. Then $V\left(G\right)={\displaystyle {\cup }_{j=0}^{4\left(q-1\right)}{S}_j}$ . By function f we have

${\chi }_2\left(G\right)\le 4$ (16)

From (15) and (16) we get ${\chi }_2\left(G\right)=4:n\equiv 0\left(\mathrm{mod}4\right)$ .

Case 2.2.2: r = 1. Then there are two leftover vertices in $V\left(G\right)={\displaystyle {\cup }_{j=0}^{4\left(q-1\right)}{S}_j}=\left\{a_n,b_n\right\}$ , by function f we get $f\left(a_n\right)=1$ , $f\left(b_n\right)=3$ which is a contradiction with $a_1$ and $a_3$ . So each of $a_n$ and $b_n$ needs deferent color then ${\chi }_2\left(G\right)>4$ . We define

$f_1=f\backslash \left\{a_n,a_{n-1},a_{n-2},a_{n-3},b_1,b_n,b_{n-1},b_{n-2},b_{n-3}\right\}\cup f_2$

where $f_2$ is a function with colors in the set {2, 3, 4, 5} define as follows:

$f_2\left(v\right)=\{\begin{array}{l}2:v=a_{n-1},b_{n-3},\\ 3:v=a_n,b_{n-2},\\ 4:v=a_{n-2},b_n,\\ 5:v=a_{n-3},b_{n-1},b_1.\end{array}$

Then gets ${\chi }_2\left(G\right)=5$ when $n\equiv 1\left(\mathrm{mod}4\right)$ .

Case 2.2.3: r = 2. Here, we will consider ${\chi }_2\left(P\left(10,3\right)\right)$ , {we delete the details of the general case because they are too long}.

We have ${\chi }_2\left(P\left(10,3\right)\right)\ge 5$ . Suppose ${\chi }_2\left(P\left(10,3\right)\right)=5$ . It is easy to prove that each color can be given at most to four vertices. This implies that each color has exactly four vertices. {If drawing $P_1\left(10,3\right)$ as following form: (outer cycle, inner cycle) respectively, $b_1{b}_4{b}_7{b}_{10}{b}_3{b}_6{b}_9{b}_2{b}_5{b}_8$ , $a_1{a}_4{a}_7{a}_{10}{a}_3{a}_6{a}_9{a}_2{a}_5{a}_8$ such that $b_i{a}_i\in E\left(P_1\left(10,3\right)\right)$ we gets the same graph ( $P\left(10,3\right)$ , i.e., $P_1\left(10,3\right)\cong P\left(10,3\right)$ }. Furthermore, no more three vertices from (outer cycle, inner cycle) respectively, can be take the same color.

Assume that there are five sets of colors, D₁, D₂, D₃, D₄, D₅, i.e., f(v) = i if and only $v\in D_i$ ( $1\le i\le 5$ ). We will study the cases for one of D_i. If D_i contain r vertices of outer cycle and q vertices of inner cycle, then we called D_i is (r-outer, q-inner). Without loss of generality, we consider D₁. Thus, we distinguish two cases:

Case a: D₁ is (3-outer, 1-inner).

(This Case is similar by symmetry to D₁ is (1-outer, 3-inner).

Let’s start with $a_1$ then we have (up to isomorphism) $D_1=\left\{a_1,a_4,a_7,b_9\right\}$ , $a_2\in D_2$ , and $a_3\in D_3$ . Thus, $b_2\in D_4$ or $b_2\in D_5$ and $b_3\in D_4$ or $b_3\in D_5$ . We have two cases:

Case a.1: $b_2\in D_4$ and $b_3\in D_5$ or $b_2\in D_5$ and $b_3\in D_4$ . Two cases are similar by symmetry. Let $b_2\in D_4$ and $b_3\in D_5$ . Then $b_6\in D_2$ , $a_5\in D_5$ , $b_5\in D_3$ , $b_8\in D_2$ , $b_4\in D_4$ . Then $b_{10}\notin D_i,\left(1\le i\le 5\right)$ , a contradiction with our hypothesis, ${\chi }_2\left(P\left(10,3\right)\right)=5$ .

Case a.2: $b_2$ and $b_3$ are belonging to the same set, let $b_2,b_3\in D_4$ . There are two subcases $a_5\in D_2$ or $a_5\in D_5$ :

Case a.2.1: $a_5\in D_2$ . Then $b_6\in D_5$ , $b_{10}\in D_2$ , $a_6\in D_3$ , $b_5\in D_5$ , $b_7\in D_5$ , $b_4\in D_4$ , $b_1\in D_3$ . So, $b_8\notin D_i,\left(1\le i\le 5\right)$ , a contradiction with ${\chi }_2\left(P\left(10,3\right)\right)=5$ .

Case a.2.2: $a_5\in D_5$ . Then $b_5\in D_3$ , $b_6\in D_2$ . This implies that $a_6\notin D_i,\left(1\le i\le 5\right)$ , again gets a contradiction with ${\chi }_2\left(P\left(10,3\right)\right)=5$ .

Case b: D₁ is (2-outer, 2-inner).

Assume that $a_1\in D_1$ . We have three cases to choose the second vertex from outer cycle.

Case b.1: $a_4\in D_1$ . (We have the same result if we take $a_8\in D_1$ ). Just one of $b_6$ , $b_9$ can belongs to $D_1$ . So, $D_1$ has three vertices and that means a contradiction with our proof that each set is from size 4.

Case b.2: $a_5\in D_1$ . (We have the same result if we take $a_7\in D_1$ ). Then $D_1=\left\{a_1,a_5,b_7,b_9\right\}$ , $a_2\in D_2$ , $a_3\in D_3$ , $a_4\in D_4$ , $b_3\in D_5$ . Also, $b_4\in D_2$ or $b_4\in D_5$ .

Case b.2.1: $b_4\in D_2$ . Then $b_{10}\in D_4$ , $b_6\in D_2$ , $a_6\in D_3$ , $b_5\in D_5$ , $a_7\in D_5$ , $b_1\in D_3$ , $b_8\in D_4$ . Thus, $b_2\notin D_i,\left(1\le i\le 5\right)$ , a contradiction with ${\chi }_2\left(P\left(10,3\right)\right)=5$ .

Case b.2.2: $b_4\in D_5$ . Then $b_1\in D_3$ , $a_{10}\in D_4$ , $b_{10}\in D_2$ , $b_5\in D_5$ , $b_2\in D_4$ . Thus, we get $b_6\notin D_i,\left(1\le i\le 5\right)$ , a contradiction with ${\chi }_2\left(P\left(10,3\right)\right)=5$ .

Case b.3: $a_6\in D_1$ . Then no vertex in inner cycle can take the color 1. We get a contradiction with our proof that each set is from size 4.

Finally, we conclude that ${\chi }_2\left(P\left(10,3\right)\right)>5$ . To prove that ${\chi }_2\left(P\left(10,3\right)\right)\le 6$ , we take a function $f:V\left(G\right)\to \left\{1,2,3,4,5,6\right\}$ as follows:

$f\left(v\right)=\{\begin{array}{l}1:v=a_1,a_5,a_8,b_3,\\ 2:v=a_2,a_6,a_9,b_4,\\ 3:v=a_3,a_7,b_1,\\ 4:v=a_4,a_{10},b_2,\\ 5:v=b_5,b_6,b_7,\\ 6:v=b_8,b_9,b_{10}.\end{array}$

Then we get ${\chi }_2\left(G\right)=6$ when $n\equiv 2\left(\mathrm{mod}4\right)$ . See Figure 5.

Case 2.2.4: r = 3. we have two subcases:

Case 2.2.4.1: r = 3 and n > 7. The contradiction in $a_n$ , $b_{n-1}$ , $b_{n-2}$ and $b_n$ . We define

$f_1=f\backslash \left\{a_n,b_n,b_{n-1},b_{n-2}\right\}\cup f_2$

where $f_2$ is a function with colors in the set {4, 5}, define as follows:

Figure 5. ${\chi }_2\left(P\left(10,3\right)\right)=6$ .

$f_2\left(v\right)=\{\begin{array}{l}4:v=a_n,\\ 5:v=b_n,b_{n-1},b_{n-2}.\end{array}$

Then we get ${\chi }_2\left(G\right)=5$ when $n\equiv 3\left(\mathrm{mod}4\right)$ for n > 7.

Case 2.2.4.2: r = 3 and n = 7. In this case we have $C_5$ induced subgraph from $P\left(7,3\right)$ . Furthermore, ${\chi }_2\left(P\left(7,3\right)\right)\ge 5$ . Let take the cycle $a_1{a}_2{b}_2{b}_5{b}_1$ and give it the fife color as follows: $f\left(a_1\right)=1$ $f\left(a_2\right)=2$ , $f\left(b_2\right)=3$ , $f\left(b_5\right)=4$ , $f\left(b_1\right)=5$ , so for $a_3$ there are two cases $f\left(a_3\right)=4$ or 5.

Case 2.2.4.2.a: $f\left(a_3\right)=4$ . Then for $b_3$ we have two choices 1 or 5. For the first choice $f\left(b_3\right)=1$ we get $f\left(a_4\right)=3$ , $f\left(b_4\right)=2$ , $f\left(a_5\right)=1$ . But for $a_6$ there are two colors 2 or 5. If $f\left(a_6\right)=5$ , then we will need a new color for $b_6$ . Also, if $f\left(a_6\right)=2$ then $f\left(b_6\right)=5$ . Obviously, we need a new color for $b_7$ . For second choice $f\left(b_3\right)=5$ then $f\left(a_4\right)=1$ or $f\left(a_4\right)=3$ . If $f\left(a_4\right)=1$ we have for $b_4$ two colors 2 or 3 if we take the color 2 then needs a new color for the vertices $a_5$ . Also, if we take the color 3 we will need a new color for $a_6$ because $a_5$ can only take the color 2. If $f\left(a_4\right)=3$ then $f\left(b_4\right)=2$ , $f\left(a_5\right)=1$ , $f\left(a_6\right)=2$ . Moreover, we will need a new color for $b_6$ .

Case 2.2.4.2.b: $f\left(a_3\right)=5$ then for $b_3$ we have two choices 1 or 4. For $f\left(b_3\right)=1$ we get $f\left(a_4\right)=3$ , $f\left(b_4\right)=2$ , $f\left(a_5\right)=1$ , $f\left(a_6\right)=5$ Then we need a new color for $b_6$ . For second choice $f\left(b_3\right)=4$ then $f\left(a_4\right)=1$ or $f\left(a_4\right)=3$ . If $f\left(a_4\right)=1$ , then we have for $b_4$ two colors 2 or 3. If we take the color 2 we will need a new color for the vertices $a_5$ . Also, if we take the color 3 we will need a new color for $a_7$ . If $f\left(a_4\right)=3$ , then $f\left(b_4\right)=2$ ,so we will need a new color for $b_7$ . We conclude that for all the cases, needs six colors. Furthermore, ${\chi }_2\left(P\left(7,3\right)\right)>5$ . To prove that ${\chi }_2\left(P\left(7,3\right)\right)\le 6$ , we take a function $f:V\left(G\right)\to \left\{1,2,3,4,5,6\right\}$ as follows:

$f\left(a_1\right)=f\left(a_5\right)=f\left(b_3\right)=1$ , $f\left(a_2\right)=f\left(a_6\right)=f\left(b_4\right)=2$ , $f\left(b_1\right)=f\left(a_3\right)=3$ ,

$f\left(b_2\right)=f\left(a_4\right)=f\left(a_7\right)=4$ , $f\left(b_5\right)=f\left(b_7\right)=5$ , $f\left(b_6\right)=6$ .

Finally, we get ${\chi }_2\left(P\left(7,3\right)\right)=6$ .

Acknowledgements

The authors would like to thank the referees for their careful reading of the paper and their helpful comments.

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	Kramer, F. and Kramer, H. (1969) Un probleme de coloration des sommets d’un graphe. C. R. Acad. Sci. Paris A, 268, 46-48.
[2]	Kramer, F. and Kramer, H. (1969) Ein Fäbungsproblem der Knotenpunkte eines Graphen bezülich der Distanz p. Rev. Roumaine Math. Pures Appl., 14, 1031-1038.
[3]	Wegner, G. (1977) Graphs with Given Diameter and a Coloring Problem. Technical Report, University of Dortmond, Dortmond, Germany.
[4]	Alon, N. and Mohar, B. (2002) The Chromatic Number of Graph Powers. Combinatorics, Probability and Computing, 11, 1-10. https://doi.org/10.1017/S0963548301004965
[5]	Bonamy, M., Lévêque, B. and Pinlou, A. (2011) 2-Distance Coloring of Sparse Graphs. Electronic Notes in Discrete Mathematics, 38, 155-160. https://doi.org/10.1016/j.endm.2011.09.027
[6]	Okamoto, F. and Zhang, P. (2010) A Note on 2-Distance Chromatic Numbers of Graphs. AKCE J. Graphs. Combin, 7, 5-9.
[7]	Jacko, P. and Jendrol, S. (2005) Distance Coloring of the Hexagonal Lattice. Discussiones Mathematicae Graph Theory, 25, 1-xxx. https://doi.org/10.7151/dmgt.1269
[8]	Borodin, O.V. and Ivanova, A.O. (2009) 2-Distance (Δ + 2)-Coloring of Planar Graphs with Girth Six and Δ ≥ 18. Discrete Mathematics, 309, 6496-6502. https://doi.org/10.1016/j.disc.2009.06.029
[9]	Dantas, S., de Figueiredo, C.M.H., Mazzuoccoloc, G., Preissmann, M., dos Santos, V.F. and Sasaki, D. (2016) On the Total Coloring of Generalized Petersen Graphs. Discrete Mathematics, 339, 1471-1475. https://doi.org/10.1016/j.disc.2015.12.010
[10]	Miao, L. and Fan, Y. (2014) The Distance Coloring of Graphs. Acta Mathematica Sinica, English Series, 30, 1579-1587. https://doi.org/10.1007/s10114-014-3238-9
[11]	Havet, F., van den Heuvel, J., McDiarmid, C. and Reed, B. (2007) List Colouring Squares of Planar Graphs. Electronic Notes in Discrete Mathematics, 29, 515-519.
[12]	Ito, T., Kato, A., Zhou, X. and Nishizeki, T. (2007) Algorithms for Finding Distance-Edge-Colorings of Graphs. Journal of Discrete Algorithms, 5, 304-322.
[13]	Kramer, F. and Kramer, H. (2008) A Survey on the Distance-Colouring of Graphs. Discrete Mathematics, 308, 422-426.
[14]	Borodin, O.V. (2013) Colorings of Plane Graphs: A Survey. Discrete Mathematics, 313, 517-539.
[15]	Shao, Z. and Vesel, A. (2013) A Note on the Chromatic Number of the Square of the Cartesian Product of Two Cycles. Discrete Mathematics, 313, 999-1001.