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
. 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
.
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
that Alice in her rth turn colors the vertex vi with a color
.
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
and the maximum degree is
. A graph G is regular if
and it’s r-regular if
.
For integers n, k (
), a generalized Petersen graph
as it defined in [3], the vertex set is
where
and
and its edge set is
, where
and subscripts are reduced modulo n.
Let
and
be positive integers and let the set
. A circulant graph
is an undirected graph of n vertices in which the ith vertex is adjacent to the (i + j)th and (i − j)th vertices for each j in the set S. The circulant graph
gives the complete graph
and the graph
gives the circle graph
. Through this paper we will denote the vertices set as
by exchanging the subscript of the vertex
by
. For further information on the chromatic number of circulant graphs see [4].
Obvious bounds of the game chromatic number are
, [1]. In [5], Faigle et al. studied the game chromatic number of tree graphs and proved that
. In [6], Bartnicki et al. studied the game chromatic number of cartesian product of two graphs and showed that
.
In [7], Destacamento et al. gave the following results:
Proposition 1.1 [7]. Let
be a path of order
then
Proposition 1.2 [7]. Let
be a cycle of order
then
.
Proposition 1.3 [7]. Let
be a complete bipartite graph then
Proposition 1.4 [6]. For any integer
,
.
In [4], the following Lemma is mentioned:
Lemma 1.1 [4]. Let
be a properly given circulant and
, Then the graph
is isomorphic to the graph
.
2. Game Chromatic Number of Circulant Graph
In this section, we found the game chromatic number for
where
.
Lemma 2.1. For n is odd,
.
Proof. Let
and
. Then
So by Lemma 1.1,
, where
is an integer satisfy that
. Then
. Hence
and
because of
. □
Lemma 2.2. For any integers
,
if
and
.
Proof. Trivial by Lemma 1.1. □
Theorem 2.1.
Proof. We will consider the cases
,
,
and
:
Case 1.
or
. Then
then
.
Case 2.
or
. In general
are 4-regular graphs so
. We will prove that no winning strategy for Alice using only four colors. Let the color set
and without loss of generality, suppose that Alice starts with
as the following:
and
now the vertices
making a cycle C4 with only two legal colors {3, 4}. By Proposition 1.2,
, so Alice will lose the game.
Case 3.
. Without loss of generality suppose that Alice starts with v1 as the following:
and
. Now let us discuss the third move which any of the following subcases:
1)
then
and now there are two critical vertices
so Alice will lose the game.
2)
then
and now there are two critical vertices
and Alice also loses the game.
3)
then
and now there are two critical vertices
so Alice also loses the game.
4)
then
and now there are two critical vertices
so Alice also loses the game.
Case 4.
. Without loss of generality, we suppose that Alice start with v1 as the following:
and
, now let us discuss the third move which any of the following subcases:
1)
then
and now there is the path
with only two legal colors {3, 4} and as Proposition 1.1,
so Alice will lose the game.
2)
then
and now similarly of last case there is the path
with only two legal colors {3, 4} and
so Alice will lose the game.
3)
where
and
then Bob’s second turn B2 will color in the opposite side one of the vertices
and as we show that will create a path P4 with only two legal colors so Alice will lose the game.
So Alice will lose with only four colors if
, then
. Hence
□
Proposition 2.1. If
and
then
Proof. Immediately by Lemma 2.2. □
Theorem 2.2.
Proof. For
, we have three cases:
Case 1.
, We have
and by Proposition 1.3, get
.
Case 2.
and
, it is 3-regular graph so
. Hence
. Now, suppose the color set is
. Without loss of generality let
and
where
. Then we have two critical vertices
as it is appeared in Figure 1. Then whatever the move A2, Alice will lose the game so
, therefore
.
Case 3.
for
. By Lemma 2.1, we have
Figure 1. A1: v1¬1, B1: vt¬2. Two critical vertices {vn, vt+1}.
. So
for odd
. □
3. Game Chromatic Number of Petersen Graph
Theorem 3.1. For
and
, we have
.
Proof. We know that generalized Petersen graphs are 3-regular graphs, so
. 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
.
Case 1.
. Petersen graph
is isomorphic to the cartesian product of K2 and a cycle Cn. By Proposition 1.4, we get
.
Case 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
then
; then v2 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.
; then
and this makes two critical vertices
and Alice cannot defend them together, for example if she defends vn and then after Bob turn will be no legal colors for u2 so she will lose the game.
Subcase 2.2.
; then
that makes v4 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 v4 that will make u4 critical so Alice lose. Now whatever Alice’s third move is,
; then we have two critical vertices {u1, u5}. 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
; then
; then v1 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.
; then
and this makes two critical vertices
and Alice cannot defend them together so she will lose the game.
Subcase 2.4.
; then
that makes u2 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 u2 that will make un critical so Alice lose. Now whatever Alice’s third move is,
; then we have two critical vertices {u3, v4}. So Alice loses with three colors in this situation. As we show with 3 colors, Alice doesn’t have any winning strategy; then
.
Case 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
; then
; then v2 is critical vertex. So Alice is forced to defend it in her second turn and whatever the second turn of Alice is, then
and this makes two critical vertices {vn, u3} 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
; then
; then v1 is critical vertex. So Alice is forced to defend it in her second turn. Whatever Alice’s second turn is, then
and this makes two critical vertices {v3, u4}. 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
. Hence
for
and
. □