ISSN 2148-838Xhttp://dx.doi.org/10.13069/jacodesmath.458240 J. Algebra Comb. Discrete Appl. 5(3) • 129–136 Received: 17 February 2017 Accepted: 10 April 2018 Journal of Algebra Combinatorics Discrete Structures and Applications Game chromatic number of Cartesian and corona product graphs Research Article Syed Ahtsham Ul Haq Bokhary, Tanveer Iqbal, Usman Ali Abstract: The game chromatic number χg is investigated for Cartesian product G�H and corona product G◦H of two graphs G and H. The exact values for the game chromatic number of Cartesian product graph of S3�Sn is found, where Sn is a star graph of order n+1. This extends previous results of Bartnicki et al. [1] and Sia [5] on the game chromatic number of Cartesian product graphs. Let Pm be the path graph on m vertices and Cn be the cycle graph on n vertices. We have determined the exact values for the game chromatic number of corona product graphs Pm ◦ K1 and Pm ◦ Cn. 2010 MSC: 05C15, 05C65 Keywords: Game chromatic number, Cartesian product, Corona product 1. Introduction We consider the following well-known graph coloring game, played on a simple graph G with a color set C of cardinality k. Two players, Alice and Bob, alternately color an uncolored vertex of G with a color from C such that no adjacent vertices receive the same color (such a coloring of a graph G is known as proper coloring). Alice has the first move and the game ends when no move is possible any more. If all the vertices are properly colored, Alice wins, otherwise Bob wins. The game chromatic number of G, denoted by χg(G), is the least cardinality k of the set C for which Alice has a winning strategy. In other words, necessary and sufficient conditions for k to be the game chromatic number of a graph G are: i) Bob has winning strategy for k − 1 colors or less and ii) Alice has winning strategy for k colors. This parameter is well defined, since it is easy to see that Alice always wins if the number of colors is larger than the maximum degree of G. Clearly, χg(G) is at least as large as the ordinary chromatic number χ(G), but it can be considerably more. For example, let G be a complete bipartite graph Kn,n Syed Ahtsham Ul Haq Bokhary (Corresponding Author), Tanveer Iqbal, Usman Ali; Centre for Advanced Studies in Pure and Applied Mathematics, Bahauddin Zakariya University, Multan, Pakistan (email: siht- sham@gmail.com, tanveerm8@yahoo.com, uali@bzu.edu.pk). 129 S. A. H. Bokhary et al. / J. Algebra Comb. Discrete Appl. 5(3) (2018) 129–136 minus a perfect matching M and consider the following strategy for Bob. If Alice colors vertex v with color c then Bob responds by coloring the vertex u matched with v in the matching M with the same color c. Note that now c cannot be used on any other vertex in the graph. Therefore, if the number of colors is less than n, Bob wins the game. This shows that there are bipartite graphs with arbitrarily large game chromatic number and thus there is no upper bound on χg(G) as a function of χ(G). The obvious bounds for the game chromatic number are: χ(G) ≤ χg(G) ≤ ∆(G) + 1 (1) where χ(G) is the chromatic number and ∆(G) is the maximum degree of the graph G. A lot of attempts have been made to determine the game chromatic number for several classes of graphs. This work was first initiated by Faigle et al. [3]. It was proved by Kierstead and Trotter [4] that the maximum of the game chromatic number of a forest is 4, also that 33 is an upper bound for the game chromatic number of planar graphs. Bodlaender [2], found that the game chromatic number of Cartesian product is bounded above by constant in the family of planar graphs. Later, Bartnicki et al. [1] determine the exact values of χg(G�H) when G and H belong to certain classes of graphs, and showed that, in general, the game chromatic number χg(G�H) is not bounded from above by a function of game chromatic numbers of the graphs G and H. After that, Zhu [6] established a bound for game coloring number and acyclic chromatic number for Cartesian product of two graphs H and S. Sia [5] determined the exact values for the Cartesian product of different families of graph like Sm�Pn, Sm�Cn, P2�Wn , where Pn, Cn, denotes the path graph and cycle graph with n vertices, respectively. While Sm is a star graph with m + 1 vertices and Wn is a wheel graph with n + 1 vertices. In this work, we have extended the study of game chromatic number and found the exact values of the game chromatic number of S3�Sn, Pm ◦K1 and Pm ◦Cn, where ◦ denote corona product of graphs. 2. Exact value of χg(S3�Sn) A Cartesian product of two graphs G and H, denoted by G�H, is the graph with vertex set V (G)× V (H), where two vertices (u,u′) and (v,v′) are adjacent if and only if u = v and u′v′ ∈ E(H) or u′ = v′ and uv ∈ E(G). Note that the Cartesian product operation is both commutative and associative up to isomorphism. Before stating our results, we introduce some definitions and notational conventions. Suppose that Alice and Bob plays the coloring game with k colors. We say that there is a threat to an uncolored vertex v if there are k − 1 colors in the neighborhood of v, and it is possible to color a vertex adjacent to v with the last color, so that all k colors would then appear in the neighborhood of v. The threat to the vertex v is said to be blocked if v is subsequently assigned a color, or it is no longer possible for v to have all k colors in its neighborhood. We shall also use the convention that color numbers are only used to differentiate distinct colors, and should not be regarded as ascribed to particular colors. For example, if only colors 1 and 2 have been used so far and we introduce a new color, color 3, then color 3 can refer to any color that is not the same as color 1 or color 2. Finally, we label figures in the following manner: vertices are labeled in the form “color(player)turn”, with the information in parentheses being omitted if the same configuration can be attained in multiple ways. In the following result, we have found the exact value of χg(S3�Sn). Theorem 2.1. For integer n ≥ 3, χg(S3�Sn) = 4. Proof. First, we show that Bob has a winning strategy with three or fewer colors. We give Bob’s winning strategy when there are exactly three colors, it will be easy to see that Bob can win using the same strategy when there are fewer than three colors. Denote the vertices of S3�Sn by a1,a2, ...,an+1,b1, b2, ...,bn+1,c1,c2, ...,cn+1,d1,d2, ....dn+1. The vertex a1 has degree n+ 3, three vertices b1,c1 and d1 have degree n + 1. The vertices a′is for i ≥ 2 has degree 4. While all the remaining vertices have degree two. 130 S. A. H. Bokhary et al. / J. Algebra Comb. Discrete Appl. 5(3) (2018) 129–136 The graph shown in Figure 1 is isomorphic to S3�Sn. Bob’s winning strategy with three colors: Case 1: Let D = {1, 2, 3} be set of colors. If Alice begins by playing color 1 in the vertex a1 of highest degree. Bob should plays color 2 in any of the vertex dk of degree two (say d2), see Figure 1. Alice can not block the threats to both the vertices d1 and a2, so Bob wins. a1 1A1 2B1 d2 d3d4dndn+1 c2c3c4cncn+1 b2b3b4bnbn+1 b1c1d1 a2a3 a4an an+1 Figure 1. Bob’s winning strategy in Case 1 for the graph S3�Sn Case 2: If Alice start the game by playing color 1 in any of the vertex bi, cj or dk 2 ≤ i,j,k ≤ n (say b2), Bob respond with color 2 in the vertex a1, see Figure 2. Now there are two vertices a2 and b1, which are under threat. Alice can save only one of these vertices and Bob wins the game. a1 1A12B1 d2 d3d4dndn+1 c2c3c4cncn+1 b2b3b4bnbn+1 b1c1d1 a2a3 a4an an+1 Figure 2. Bob’s winning strategy in Case 2 for the graph S3�Sn Case 3: If Alice begins the game by assigning color to any of the vertices al, 2 ≤ l ≤ n. Suppose, she plays a color 1 in the vertex a2. In response, Bob plays color 2 in the vertex ai, where i 6= 2 and i > 2 say a3. This forces Alice to assign color 3 to the vertex a1, because this is the only way, she can block the threat to this vertex. After that Bob plays color 1 in the neighbor of a′ls (l ≥ 4) and wins the games. Case 4: If Alice start the game by playing color 1 in vertex b1, c1 or d1 (say b1). Bob should plays color 2 in any of the vertices ai, where 2 ≤ i ≤ n, for simplicity, say a2. There are two distinct colors in the neighbor of vertex a1, so Alice must block the threat to this vertex by assigning it the color 3. In the next move Bob plays color 1 in dk (k 6= 2) say d3. Now Alice can’t block the threat of d1 and a3 and Bob wins the game. Thus χg(S3�Sn) ≥ 4. Next, Alice’s winning strategy is given for four colors, which proves that χg(S3�Sn) ≤ 4. Alice’s winning strategy with four colors: Alice in her strategy, first assigns colors to all the vertices of degree n + 1, because in this way, she can prevent these vertices from threats. Now al, where l ≥ 1 are 131 S. A. H. Bokhary et al. / J. Algebra Comb. Discrete Appl. 5(3) (2018) 129–136 the only vertices which can come under threat. Since al ∼ bi (l = i), al ∼ cj (l = j) and al ∼ dk (l = k). So, whenever, Bob plays a color in a vertex adjacent to ai, say cj, Alice will play the color of vertex a1 or color of the vertex cj in bi (adjacent to al). In this way, Alice can prevent these vertices from threats, since every vertex has two same colors in its neighbor. So, in order to win the game, she need only to assign colors in the vertices of degree greater than 4. Below, we have given the Alice strategy to color these vertices with four given colors. Alice makes her first move by playing color 1 in any of three vertices having degree n + 1, say b1. We, now consider all the cases for Bob’s first move. Case 1: If Bob plays color 2 in any of the vertex having degree four, say a2. Alice makes her second move by playing color 2 in the vertex c1. Now Bob has two possibilities for his second move. Case 1.1: If Bob wants that the vertex a1 be under threat in his second move and assigns color 3 to the vertex a3. Alice, then has to play color 4 in a1, in order to prevent this vertex from threat. Alice is safe to assign suitable color in the vertex d1 in her fourth move. Now all the vertices of degree greater than four have assigned color. After that whenever Bob plays a color in a vertex bi or cj say cj (adjacent to al), Alice will play the color of cj in bi where l = i = j and win the game. (strategy is shown in Figure 3) a1 d2d3d4dndn+1 c2c3c4cncn+1 b2b3b4bnbn+1 b1c1d1 a2a3 a4an an+1 1A11A22B13B2 4A3 Figure 3. Alice’s winning strategy in Case 1 for the graph S3�Sn Case 1.2: Bob plays color 1 in d′ks, say d3 which is adjacent to d1. In respond, Alice assigns color 2 in a1. In his third move Bob plays according to the following strategy. i: If Bob plays color 2 in the vertex b′is or c ′ js, Alice then plays color of the vertex cj in bi (i = j). Now vertex al (i = l = j) has two same colors in its neighbors. In this way Alice protects all the vertices of degree four from threat. Alice will play only color in a1, whenever Bob plays color in a′is. Case 2: In this case, Bob plays his first move in the vertices of degree two and assigns color 1 in dk or cj say d2. Alice then plays color 1 in c1. Now we consider all the cases for Bob’s second move. Case 2.1: If Bob plays again in the neighbor of d1 say d3 by assigning it color 2. Alice, in respond plays color 3 in d1. Now there are following possibilities of Bob’s third move. We distinguish 3 subcases. i: If Bob wants that the vertex a1 be under threat and plays color 2 in al say a2. Alice then should play color 4 in a1. Now all the vertices of degree greater than four have assigned color. After that Alice follow the same strategy as in case 1. ii: If Bob plays in the neighbor of that al which has already two distinct colors say a2 and assigns color 2 in bi or cj say c2. Alice can prevent this vertex from threat by playing color of vertex c2 in vertex b2. After that Alice follows the same strategy as in case 1. iii: If Bob wants to plays in the neighbor of that al which has has no color assigned say a4 and assigns color 1 in d4 (d4 is adjacent to a4), then Alice plays color 2 or color 4 in the vertex a1. In his next move if, Bob again plays in the neighbor of a4 and assigns color 3 in c4. Alice then should play color of c4 in b4. Now a4 has two same colors in its neighbor. Whenever, Bob plays color 1 in any one of the remaining uncolored dk′s say d5, Alice then plays color of vertex a1 in c5. Now there are two same colors in the 132 S. A. H. Bokhary et al. / J. Algebra Comb. Discrete Appl. 5(3) (2018) 129–136 a1 d2d3d4dndn+1 c2c3c4cncn+1 b2b3b4bnbn+1 b1c1d1 a2a3 a4an an+1 1A11A2 2B3 3A3 4A4 1B1 2B2 Figure 4. Alice’s winning strategy in Case 2 for the graph S3�Sn neighbor of a5. After that Alice follow the same strategy as in case 1. Case 2.2: Now vertices d1 and a2 have one color in its neighbor. If Bob make his second move by playing the color 2 in bi or cj say c2, then Alice assigns color of vertex c2 in b2. In this way, Alice can block the threat of vertex a2. After that Alice follows the same strategies as in case 1 and case 2.1. Case 2.3: If Bob plays suitable color in cj or bi say cj (k 6= j), then Alice plays color of that cj in bi (i = j). After that Alice follows the same strategies as in above cases. Case 3: If Alice assigns color 1 in b1 in her first move and Bob plays color 2 in c1. Alice then plays color in d1. Now all the vertices of degree n + 1 have colored. After that Alice will follow the strategy of case 1 and case 2 in her next moves to win the game. Case 4: Bob plays color 2 in the vertex a1 in his first move. Alice then plays color 1 in c1. Now, irrespective of Bob’s next move. Alice plays color 3 in d1. In this way, Alice can succeed to assign color to all the vertices of degree greater than n + 1. Now Bob will in bi or cj or dk to create threat in al. Alice will respond by following the strategies of case 1 and case 2 and she wins the game. 3. Exact values of χg(Pm ◦K1) and χg(Cm ◦Pn) Let G and H be two graphs of order n1 and n2, respectively. The corona product G◦H is defined as the graph obtained from G and H by taking one copy of G and n1 copies of H and joining by an edge each vertex from the ith−copy of H with the ith−vertex of G. We will denote by V = {v1,v2, . . . ,vn} the set of vertices of G and by Hi = (Vi,Ei) the copy of H such that vi ∼ v for every v ∈ Vi. It is important to note that the corona product operation is not commutative. In this section we prove the exact values of χg(Pm ◦K1) and χg(Cm ◦Pn). Theorem 3.1. The game chromatic number of Pm ◦K1 = 3, where m ≥ 2. Proof. It is obvious that χg(Pm ◦ K1) ≥ 3. In order to show that χg(Pm ◦ K1) ≤ 3, Alice winning strategy is given. Alice’s winning strategy with 3 colors: Alice starts the game by playing color 1 in the vertex w1. Suppose, in his first move, Bob plays one of the available color in vertex vi, then Alice responds by playing the same color in wi+1 or wi−1 . In this way she can block the threat to the vertex vi, because it has two same colors in its neighbor. Similarly if Bob plays some color in vertex wi, Alice responds by playing the same color in vi+1 or vi−1. If during the game the following two cases arises, then Alice will play according to the following strategy. Case 1: Suppose the vertex vj is already colored and Bob plays a color in the vertex wi. In this 133 S. A. H. Bokhary et al. / J. Algebra Comb. Discrete Appl. 5(3) (2018) 129–136 situation, If d(vi, vm) is odd then Alice assigns the same color in vi−1 (if i > j) or vi+1 (if i < j), otherwise she plays any available color in the vertex vi. Case 2: If there are two vertices say vm and vn that are already colored and Bob plays a color 1 in the vertex wi where m < i < n. In response, Alice plays the same color 1 in vi−1, (if d(vi, vm) is even) or in vi+1 (if d(vi, vn) is even). In case when vi is at odd distance to both vm and vn, she will play any available color in the vertex vi. Similarly if Bob plays some color in vi then Alice plays the same color in wi−1 or wi+1 according to the above two cases. If during the game, the following situations arise then Alice modifies her strategy according to the situation. Situation 1: A part of graph Pm ◦K1 is shown in Figure 5. If Bob plays the color 3 on wi+2. Suppose, Bob already assigned the color 3 in the vertex vi+4. Then vi vi+1 vi+2 vi+3 wi+1 wi+2 wi+3 wi+4 vi+4 vi+5 3B 3Bi 2Ai+1 3A wi 2A 2B Figure 5. P3 ◦ K1 according to her strategy Alice can not assign the same color in the vertex vi+3. In this case Alice plays color 2 in vi+3, because this is the only way she can block the threat to the vertex vi+2. Situation 2: If Bob plays a color (say 3) in the vertex wi+2 and the vertices vi+4 and vi−1 are already colored with colors 3 and 2 respectively. In this situation Alice plays the same color as of the vertex vi−1 in wi. vi vi+1 vi+2 vi+3 wi+1 wi+2 wi+3 wi+4 vi+4 vi+5 2A 3B 3Bi2Ai+1 3A2B wiwi-1wi-2 vi-1 1Bi+1 1Ai+2 Figure 6. P3 ◦ K1 Theorem 3.2. For any integer n ≥ 2 and m ≥ 3 we have that χg(Cm ◦Pn) = 4. 134 S. A. H. Bokhary et al. / J. Algebra Comb. Discrete Appl. 5(3) (2018) 129–136 Proof. The graph C8 ◦Pn is shown in the Figure 7. Bob’s winning strategy for 3 colors: a1 a2 a3 a4 a5 a6 a7 a8 b1,1 b1,n b8,1 b8,n 1A1 2B1 3A2 3A3 1B2 3A4 2B3 3B4 Figure 7. C8 ◦ Pn Case 1: Alice makes her first move by playing color 1 in any of the vertex from the inner cycle, say a1. In response Bob plays the color 2 in the vertex a3. In her second move Alice will play color 3 in the vertex a2 because this is the only way she can block the threat to this vertex. In his next moves Bob plays suitable color in the alternative vertices a5,a7,a9, . . . , respectively, forcing Alice to play suitable color in the vertices a4,a6,a8, . . . . Continuing in this way, Bob plays his last move according to the following two situations: i: If the number of vertices in inner cycle are even then Bob plays any suitable color in the vertex an−1. Alice cannot block the threat to both the vertices an−2 and an, and Bob wins. ii: If the number of vertices in inner cycle are odd then Bob in his second last move plays a color in any of the vertex bi,n−1, which is different to that of a1. In response Alice is forced to play color in the vertex an−1 because this is the only way to block the threat to this vertex. By playing a color different to both a1 and an−1 in any of the vertex bi,n−1, Bob can succeed to assign three distinct colors in the neighbor of the vertex an. Case 2: Alice makes her first move by playing color 1 in any of the outer vertex bi,n, say b1,1. In response Bob plays color 2 in the vertex b2,1. In her second move Alice has to play color 3 in the vertex a1 because this is the only way she can block the threat to this vertex. In his next moves, Bob plays in the alternative vertices a3,a5,a7, . . . , respectively, forcing Alice to play in the vertices a2,a4,a6, . . . Continuing in this way, Bob plays his last move according to Case 1. Hence χg(Cm ◦Pn) ≥ 4. Alice’s winning strategy with 4 colors: The graph Cm ◦Pn have m + mn vertices. The vertices of degree greater than four are only the vertices of the inner cycle, as shown in the above Figure. Alice, in her strategy assigns color to the vertices a1,a2, ...,am and consequently blocks the threat to these vertices. Since Alice has to start the game, 135 S. A. H. Bokhary et al. / J. Algebra Comb. Discrete Appl. 5(3) (2018) 129–136 suppose she makes her first move by playing color 1 in the vertex a1. In respond, Bob can play the game in the following two ways. Case 1: Bob plays in the vertices of inner cycle say ai, for some 2 ≤ i ≤ m. Alice responds by playing any color from the set of available colors in the uncolored vertices of inner cycle. Case 2: Bob plays in the vertices bi,j, then Alice assigns a suitable color in the corresponding ai. Bob can only win if he succeeded to assign 4 distinct colors in the neighborhood of any vertex. But whenever he plays in the outer vertices, bi,j, Alice assigns a suitable color in the corresponding ai. In this way Alice can color all the vertices in the inner cycle and she wins the game. From both these strategies we conclude that χg(Cm ◦Pn) = 4. Acknowledgment: The authors are very thankful to a referee for careful reading with corrections and useful comments. References [1] T. Bartnicki, B. Brešar, J. Grytczuk, M. Kovše, Z. Miechowicz, I. Peterin, Game chromatic number of Cartesian product graphs, Electron. J. Combin. 15 (2008) R72. [2] H. L. Bodlaender, On the complexity of some coloring games, Int. J. Found. Comput. Sci. 2(2) (1991) 133–147. [3] U. Faigle, U. Kern, H. Kierstead, W. T. Trotter, On the game chromatic number of some classes of graphs, Ars Combin. 35 (1993) 143–150. [4] H. A. Kierstead, W. T. Trotter, Planar graph coloring with uncooperative partner, J. Graph Theory 18(6) (1994) 569–584. [5] C. Sia, The game chromatic number of some families of Cartesian product graphs, AKCE Int. J. Graphs Comb. 6(2) (2009) 315–327. [6] X. Zhu, Game coloring the Cartesian product of graphs, J. Graph Theory 59(4) (2008) 261–278. 136 https://mathscinet.ams.org/mathscinet-getitem?mr=2411449 https://mathscinet.ams.org/mathscinet-getitem?mr=2411449 https://doi.org/10.1142/S0129054191000091 https://doi.org/10.1142/S0129054191000091 https://mathscinet.ams.org/mathscinet-getitem?mr=1220515 https://mathscinet.ams.org/mathscinet-getitem?mr=1220515 https://mathscinet.ams.org/mathscinet-getitem?mr=1292976 https://mathscinet.ams.org/mathscinet-getitem?mr=1292976 https://mathscinet.ams.org/mathscinet-getitem?mr=2549583 https://mathscinet.ams.org/mathscinet-getitem?mr=2549583 https://mathscinet.ams.org/mathscinet-getitem?mr=2463181 Introduction Exact value of g(S3Sn) Exact values of g(PmK1) and g(CmPn) References