Game Chromatic Number of Some Regular Graphs

Show more

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 \mathrm{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{\hspace{0.17em}}\text{\hspace{0.17em}}\text{if}\text{\hspace{0.17em}}n=2\text{\hspace{0.17em}}\text{or}\text{\hspace{0.17em}}3,\\ 3;\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\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{\hspace{0.17em}}\text{\hspace{0.17em}}\text{if}\text{\hspace{0.17em}}\mathrm{min}\left\{m,n\right\}=1,\\ 3;\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\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 $\mathrm{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}\mathrm{gcd}\left(n,a\right)=\mathrm{gcd}\left(n,\frac{n-1}{2}\right)=\mathrm{gcd}\left(n-\frac{n-1}{2},\frac{n-1}{2}\right)\\ =\mathrm{gcd}\left(\frac{n+1}{2},\frac{n-1}{2}\right)=\mathrm{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 $\mathrm{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{\hspace{0.17em}}\text{\hspace{0.17em}}\text{if}\text{\hspace{0.17em}}n=4,\\ 5\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{if}\text{\hspace{0.17em}}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_{4} 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_{1} 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_{1} 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_{2} 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_{4} 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{\hspace{0.17em}}\text{\hspace{0.17em}}\text{if}\text{\hspace{0.17em}}n=4,\\ 5\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{if}\text{\hspace{0.17em}}n\ge 5.\end{array}$ □

Proposition 2.1. If $\mathrm{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{\hspace{0.17em}}\text{\hspace{0.17em}}\text{if}\text{\hspace{0.17em}}n=4,\\ 5\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{if}\text{\hspace{0.17em}}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{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.05em}}\text{\hspace{0.05em}}\text{if}\text{\hspace{0.17em}}n=6,\\ 4\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{for}\text{\hspace{0.17em}}\text{even}\text{\hspace{0.17em}}n\ne 6,\\ 5\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\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_{2}, 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_{1}: v_{1}¬1, B_{1}: 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_{2} 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_{2} 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_{2} 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_{4} 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_{4} that will make u_{4} critical so Alice lose. Now whatever Alice’s third move is,
${B}_{3}:{u}_{3}\leftarrow 3$ ; then we have two critical vertices {u_{1}, u_{5}}. 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_{1} 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_{2} 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_{2} 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_{3}, v_{4}}. 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_{2} 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_{3}} 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_{1} 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_{3}, u_{4}}. 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\}$. □

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.