Game Chromatic Number of Some Regular Graphs

Ramy Shaheen, Ziad Kanaya, Khaled Alshehada

Department of Mathematics, Tishreen University, Lattakia, Syria.

DOI: 10.4236/ojdm.2019.94012                

Abstract

Let G be a graph and k be a positive integer. We consider a game with two players Alice and Bob who alternate in coloring the vertices of G with a set of k colors. In every turn, one vertex will be chosen by one player. Alice’s goal is to color all vertices with the k colors, while Bob’s goal is to prevent her. The game chromatic number denoted by χ_g(G), is the smallest k such that Alice has a winning strategy with k colors. In this paper, we determine the game chromatic number χ_g of circulant graphs C_n(1,2), , and generalized Petersen graphs GP(n,2), GP(n,3).

Keywords

Game Chromatic Number, Circulant Graph, Generalized Petersen Graphs

1. Introduction

Game chromatic number was introduced by Bodlaender [1]. The game chromatic number is defined as a two person game Alice and Bob, and set of colors $X=\left\{1,\cdots ,k\right\}$. Players take turns to color the vertices of a given finite graph G, where no two adjacent vertices take the same color. The game starts with Alice, who wins the game if all the vertices of G are colored. Bob wins the game if at any stage of the game, there is an uncolored vertex without any legal colors. Suppose that the players use their optimal strategies, the minimum positive integer k such that Alice has a winning strategy is the game chromatic number and denoted by ${\chi }_g$.

The uncolored vertex u is called color i-critical as it is defined in [2], if the following holds:

1) Color i is the only available color for u.

2) Vertex u has a neighbor v such that i is available color for v.

During the game notice the following: If a vertex u is color i-critical and if it is Bob’s turn then Bob wins the game. But if it is Alice’s turn then she must defend the vertex u and make it not critical by do one of the followings:

1) Color the vertex u with the color i.

2) Choose a vertex w such that color i is available color for it and satisfy that it is adjacent to all uncolored neighbors of u which i is available color to them, and then color w with i.

3) If u has only one uncolored neighbor w available to color with i then color it with another color.

Through this paper we denoted by $A_r:v_i\leftarrow c$ that Alice in her r^th turn colors the vertex v_i with a color $c\in X$.

The degree of a vertex v is the number of non-loop edges incident on v plus twice the number of loops incident on v. The minimum degree of a graph G denoted by $\delta \left(G\right)$ and the maximum degree is $\Delta \left(G\right)$. A graph G is regular if $\delta \left(G\right)=\Delta \left(G\right)$ and it’s r-regular if $\delta \left(G\right)=\Delta \left(G\right)=r$.

For integers n, k ( $n>2k$ ), a generalized Petersen graph $GP\left(n,k\right)$ as it defined in [3], the vertex set is $V\cup U$ where $V=\left\{v_1,v_2,\cdots ,v_n\right\}$ and $U=\left\{u_1,u_2,\cdots ,u_n\right\}$ and its edge set is $E=\left\{v_i{v}_{i+1},v_i{u}_i,u_i{u}_{i+k}\right\}$, where $i=1,2,\cdots ,n$ and subscripts are reduced modulo n.

Let $n,m$ and $r,s,q,\cdots ,m$ be positive integers and let the set $S=\left\{r,s,q,\cdots ,m\right\}$. A circulant graph $C_n\left(S\right)$ is an undirected graph of n vertices in which the i^th vertex is adjacent to the (i + j)^th and (i − j)^th vertices for each j in the set S. The circulant graph $C_n\left(1,2,3,\cdots ,\lfloor \frac{n}{2}\rfloor \right)$ gives the complete graph $K_n$ and the graph $C_n\left(1\right)$ gives the circle graph $C_n$. Through this paper we will denote the vertices set as $V=\left\{v_i|i=1,\cdots ,n\right\}$ by exchanging the subscript of the vertex $v_0$ by $v_n$. For further information on the chromatic number of circulant graphs see [4].

Obvious bounds of the game chromatic number are $\chi \left(G\right)\le {\chi }_g\left(G\right)\le \Delta \left(G\right)+1$, [1]. In [5], Faigle et al. studied the game chromatic number of tree graphs and proved that ${\chi }_g\left(T\right)\le 4$. In [6], Bartnicki et al. studied the game chromatic number of cartesian product of two graphs and showed that

${\chi }_g\left(GH\right)\ge \max \left\{{\chi }_g\left(G\right),{\chi }_g\left(H\right)\right\}$.

In [7], Destacamento et al. gave the following results:

Proposition 1.1 [7]. Let $P_n$ be a path of order $n\ge 2$ then

${\chi }_g\left(P_n\right)=\{\begin{array}{l}2;\text{if}n=2\text{or}3,\\ 3;\text{otherwise}.\end{array}$

Proposition 1.2 [7]. Let $C_n$ be a cycle of order $n\ge 3$ then

${\chi }_g\left(C_n\right)=3$.

Proposition 1.3 [7]. Let $K_{m,n}$ be a complete bipartite graph then

${\chi }_g\left(K_{m,n}\right)=\{\begin{array}{l}2;\text{if}\min \left\{m,n\right\}=1,\\ 3;\text{otherwise}.\end{array}$

Proposition 1.4 [6]. For any integer $n\ge 3$, ${\chi }_g\left(K_2\square C_n\right)=4$.

In [4], the following Lemma is mentioned:

Lemma 1.1 [4]. Let $C_n\left(a,b\right)$ be a properly given circulant and $\gcd \left(n,a\right)=1$, Then the graph $C_n\left(a,b\right)$ is isomorphic to the graph $C_n\left(1,a^{-1}b\mathrm{mod}n\right)$.

2. Game Chromatic Number of Circulant Graph

In this section, we found the game chromatic number for $C_n\left(1,a\right)$ where $a\in \left\{2,\lfloor \frac{n}{2}\rfloor \right\}$.

Lemma 2.1. For n is odd, $C_n\left(1,2\right)\cong C_n\left(1,\lfloor \frac{n}{2}\rfloor \right)$.

Proof. Let $a=\lfloor \frac{n}{2}\rfloor =\frac{n-1}{2}$ and $b=1$. Then

$\begin{array}{c}\gcd \left(n,a\right)=\gcd \left(n,\frac{n-1}{2}\right)=\gcd \left(n-\frac{n-1}{2},\frac{n-1}{2}\right)\\ =\gcd \left(\frac{n+1}{2},\frac{n-1}{2}\right)=\gcd \left(\frac{n-1}{2},1\right)=1\end{array}$

So by Lemma 1.1, $C_n\left(1,\lfloor \frac{n}{2}\rfloor \right)\cong C_n\left(1,a^{-1}b\mathrm{mod}n\right)$, where $a^{-1}$ is an integer satisfy that $a{a}^{-1}\equiv 1\left(\mathrm{mod}n\right)$. Then $a^{-1}b\mathrm{mod}n=-2$. Hence $C_n\left(1,\lfloor \frac{n}{2}\rfloor \right)\cong C_n\left(1,-2\right)$ and $C_n\left(1,\lfloor \frac{n}{2}\rfloor \right)\cong C_n\left(1,2\right)$ because of $C_n\left(1,2\right)\cong C_n\left(1,-2\right)$. □

Lemma 2.2. For any integers $a,b$, $C_n\left(a,b\right)\cong C_n\left(1,2\right)$ if $\gcd \left(n,a\right)=1$ and $2a\equiv b\left(\mathrm{mod}n\right)$.

Proof. Trivial by Lemma 1.1. □

Theorem 2.1. ${\chi }_g\left(C_n\left(1,2\right)\right)=\{\begin{array}{l}4\text{if}n=4,\\ 5\text{if}n\ge 5.\end{array}$

Proof. We will consider the cases $n=4,5$, $n=6,7$, $n=8$ and $n\ge 9$ :

Case 1. $n=4$ or $n=5$. Then $C_n\left(1,2\right)\cong K_n$ then ${\chi }_g\left(C_n\left(1,2\right)\right)=n$.

Case 2. $n=6$ or $n=7$. In general $C_n\left(1,2\right)$ are 4-regular graphs so ${\chi }_g\left(C_n\left(1,2\right)\right)\le 5$. We will prove that no winning strategy for Alice using only four colors. Let the color set $X=\left\{1,2,3,4\right\}$ and without loss of generality, suppose that Alice starts with $v_1$ as the following:

$A_1:v_1\leftarrow 1$ and $B_1:v_2\leftarrow 2$ now the vertices $\left\{v_2,v_3,v_5,v_6\right\}$ making a cycle C₄ with only two legal colors {3, 4}. By Proposition 1.2, ${\chi }_g\left(C_4\right)=3>2$, so Alice will lose the game.

Case 3. $n=8$. Without loss of generality suppose that Alice starts with v₁ as the following: $A_1:v_1\leftarrow 1$ and $B_1:v_2\leftarrow 2$. Now let us discuss the third move which any of the following subcases:

1) $A_2:v_5\leftarrow 1$ then $B_2:v_8\leftarrow 3$ and now there are two critical vertices $\left\{v_2,v_6\right\}$ so Alice will lose the game.

2) $A_2:v_8\leftarrow 2$ then $B_2:v_5\leftarrow 3$ and now there are two critical vertices $\left\{v_3,v_7\right\}$ and Alice also loses the game.

3) $A_2:v_6\leftarrow 1$ then $B_2:v_3\leftarrow 3$ and now there are two critical vertices $\left\{v_2,v_5\right\}$ so Alice also loses the game.

4) $A_2:v_6\leftarrow 3$ then $B_2:v_5\leftarrow 4$ and now there are two critical vertices $\left\{v_3,v_7\right\}$ so Alice also loses the game.

Case 4. $n\ge 9$. Without loss of generality, we suppose that Alice start with v₁ as the following: $A_1:v_1\leftarrow 1$ and $B_1:v_2\leftarrow 2$, now let us discuss the third move which any of the following subcases:

1) $A_2:v_n\leftarrow 2$ then $B_2:v_7\leftarrow 1$ and now there is the path $P_4:\left\{v_2,v_3,v_5,v_6\right\}$ with only two legal colors {3, 4} and as Proposition 1.1, ${\chi }_g\left(P_n\right)=3$ so Alice will lose the game.

2) $A_2:v_5\leftarrow 1$ then $B_2:v_{n-2}\leftarrow 2$ and now similarly of last case there is the path $P_4:\left\{v_{n-1},v_n,v_2,v_3\right\}$ with only two legal colors {3, 4} and ${\chi }_g\left(P_n\right)=3$ so Alice will lose the game.

3) $A_2:v_i\leftarrow c$ where $i\notin \left\{2,3,5,n\right\}$ and $c\in X$ then Bob’s second turn B₂ will color in the opposite side one of the vertices $\left\{v_7,v_n\right\}$ and as we show that will create a path P₄ with only two legal colors so Alice will lose the game.

So Alice will lose with only four colors if $n\ge 5$, then ${\chi }_g\left(C_n\left(1,2\right)\right)>4$. Hence

${\chi }_g\left(C_n\left(1,2\right)\right)=\{\begin{array}{l}4\text{if}n=4,\\ 5\text{if}n\ge 5.\end{array}$ □

Proposition 2.1. If $\gcd \left(n,a\right)=1$ and $2a\equiv b\left(\mathrm{mod}n\right)$ then

${\chi }_g\left(C_n\left(a,b\right)\right)=\{\begin{array}{l}4\text{if}n=4,\\ 5\text{if}n\ge 5.\end{array}$

Proof. Immediately by Lemma 2.2. □

Theorem 2.2. ${\chi }_g\left(C_n\left(1,\lfloor \frac{n}{2}\rfloor \right)\right)=\{\begin{array}{l}3\text{if}n=6,\\ 4\text{for}\text{even}n\ne 6,\\ 5\text{otherwise}.\end{array}$

Proof. For $n\ge 5$, we have three cases:

Case 1. $n=6$, We have $K_{3,3}$ and by Proposition 1.3, get ${\chi }_g\left(K_{3,3}\right)=3$.

Case 2. $n=0\left(\mathrm{mod}2\right)$ and $n\ne 6$, it is 3-regular graph so $\Delta =3$. Hence ${\chi }_g\left(C_n\left(1,\lfloor \frac{n}{2}\rfloor \right)\right)\le 4$. Now, suppose the color set is $X=\left\{1,2,3\right\}$. Without loss of generality let $A_1:v_1\leftarrow 1$ and $B_1:v_t\leftarrow 2$ where $t=\frac{n}{2}$. Then we have two critical vertices $\left\{v_{t+1},v_n\right\}$ as it is appeared in Figure 1. Then whatever the move A₂, Alice will lose the game so ${\chi }_g\left(C_n\left(1,\frac{n}{2}\right)\right)>3$, therefore ${\chi }_g\left(C_n\left(1,\frac{n}{2}\right)\right)=4$.

Case 3. $n=1\left(\mathrm{mod}2\right)$ for $n\ge 5$. By Lemma 2.1, we have

Figure 1. A₁: v₁¬1, B₁: v_t¬2. Two critical vertices {v_n, v_t+1}.

$C_n\left(1,\lfloor \frac{n}{2}\rfloor \right)\cong C_n\left(1,2\right)$. So ${\chi }_g\left(C_n\left(1,\lfloor \frac{n}{2}\rfloor \right)\right)=5$ for odd $n\ge 5$. □

3. Game Chromatic Number of Petersen Graph

Theorem 3.1. For $n\ge 6$ and $k\in \left\{1,2,3\right\}$, we have ${\chi }_g\left(GP\left(n,k\right)\right)=4$.

Proof. We know that generalized Petersen graphs are 3-regular graphs, so ${\chi }_g\left(GP\left(n,k\right)\right)\le 4$. Here we are going to prove that Alice doesn’t have any winning strategy with only three colors by discussing the possible moves for each player. Assume the color set’s cardinality is 3 as $X=\left\{1,2,3\right\}$.

Case 1. $k=1$. Petersen graph $GP\left(n,1\right)$ is isomorphic to the cartesian product of K₂ and a cycle C_n. By Proposition 1.4, we get ${\chi }_g\left(GP\left(n,k\right)\right)={\chi }_g\left(K_2\square C_n\right)=4$.

Case 2. $k=2$. In general Alice has two choices to starts the game:

First choice: Alice starts with a vertex of the outer cycle:

Without loss of generality, let $A_1:v_1\leftarrow 1$ then $B_1:v_3\leftarrow 2$ ; then v₂ is critical vertex so Alice is forced to defend it in her second turn. So we will discuss second turn of Alice:

Subcase 2.1. $A_2:v_2\leftarrow 3$ ; then $B_2:u_n\leftarrow 2$ and this makes two critical vertices $\left\{v_n,u_2\right\}$ and Alice cannot defend them together, for example if she defends v_n and then after Bob turn will be no legal colors for u₂ so she will lose the game.

Subcase 2.2. $A_2:u_2\leftarrow 1$ ; then $B_2:v_5\leftarrow 1$ that makes v₄ a critical vertex so Alice will be forced to defend it by coloring it’s unique uncolored neighbor in her third move. Notice here if Alice colors v₄ that will make u₄ critical so Alice lose. Now whatever Alice’s third move is, $B_3:u_3\leftarrow 3$ ; then we have two critical vertices {u₁, u₅}. So Alice loses with three colors in this situation too.

Second choice: Alice starts with a vertex of the inner cycle:

Without losing of generality let $A_1:u_1\leftarrow 1$ ; then $B_1:v_2\leftarrow 2$ ; then v₁ is critical vertex so Alice is forced to defend it in her second turn. So we will discuss second turn of Alice:

Subcase 2.3. $A_2:v_1\leftarrow 3$ ; then $B_2:u_{n-1}\leftarrow 2$ and this makes two critical vertices $\left\{v_n,u_{n-1}\right\}$ and Alice cannot defend them together so she will lose the game.

Subcase 2.4. $A_2:v_n\leftarrow 1$ ; then $B_2:u_4\leftarrow 1$ that makes u₂ a critical vertex. So, Alice will be forced to defend it by coloring its unique uncolored neighbor in her third move. Also notice here if Alice colors u₂ that will make u_n critical so Alice lose. Now whatever Alice’s third move is, $B_3:v_3\leftarrow 3$ ; then we have two critical vertices {u₃, v₄}. So Alice loses with three colors in this situation. As we show with 3 colors, Alice doesn’t have any winning strategy; then ${\chi }_g\left(GP\left(n,k\right)\right)>3$.

Case 3. $k=3$. Also Alice has two choices to start the game:

First choice: Alice starts with a vertex of the outer cycle:

Without losing of generality let $A_1:v_1\leftarrow 1$ ; then $B_1:v_3\leftarrow 2$ ; then v₂ is critical vertex. So Alice is forced to defend it in her second turn and whatever the second turn of Alice is, then $B_2:u_n\leftarrow 2$ and this makes two critical vertices {v_n, u₃} and Alice cannot defend them together, and then she will lose the game.

Second choice: Alice starts with a vertex of the inner cycle:

Without losing of generality let $A_1:u_1\leftarrow 1$ ; then $B_1:v_2\leftarrow 2$ ; then v₁ is critical vertex. So Alice is forced to defend it in her second turn. Whatever Alice’s second turn is, then $B_2:v_4\leftarrow 3$ and this makes two critical vertices {v₃, u₄}. Then Alice cannot defend them together. Hence she will lose the game.

So as we show with 3 colors, Alice doesn’t have any winning strategy; then ${\chi }_g\left(GP\left(n,k\right)\right)>3$. Hence ${\chi }_g\left(GP\left(n,k\right)\right)=4$ for $n\ge 6$ and $k\in \left\{1,2,3\right\}$. □

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Bodlaender, H.L. (1991) On the Complexity of Some Coloring Games. In: Möhring, R.H., Ed., Graph Theoretic Concepts in Computer Science. Lecture Notes in Computer Science, Vol. 484, Springer-Verlag, Berlin, New York, 30-40. https://doi.org/10.1007/3-540-53832-1_29
[2]	Raspaud, A. and Wu, J. 2009) Game Chromatic Number of Toroidal Grids. Information Processing Letters, 109, 1183-1186. https://doi.org/10.1016/j.ipl.2009.08.001
[3]	Dantas, S., de Figueiredo, C.M.H., Mazzuoccolo, 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
[4]	Heuberger, C. (2003) On Planarity and Colorability of Circulant Graphs. Discrete Mathematics, 268, 153-169. https://doi.org/10.1016/S0012-365X(02)00685-4
[5]	Faigle, U., Kern, U., Kierstead, H.A. and Trotter, W.T. (1993) On the Game Chromatic Number of Some Classes of Graphs. Ars Combinatoria, 35, 143-150.
[6]	Bartnicki, T., Brešar, B., Grytczuk, J., Kovše, M., Miechowicz, Z. and Peterin, I. (2008) Game Chromatic Number of Cartesian Product Graphs. The Electronic Journal of Combinatorics, 15, 13.
[7]	Destacamento, C.J., Rodriguez, A.D. and Ruivivar, L.A. (2014) The Game Chromatic Number of Some Classes of Graphs. DLSU Research Congress, De La Salle University, Manila, Philippines.