# Game Chromatic Number of Generalized Petersen Graphs and Jahangir Graphs

Authors: Ramy Shaheen; Ziad Kanaya; Khaled Alshehada
Journal: Journal of Applied Mathematics
 (2020)

---

## Abstract

LetG=V,E be a graph, and two players Alice and Bob alternate turns coloring the vertices of the graph G a proper coloring where no two adjacent vertices are signed with the same color. Alice's goal is to color the set of vertices using the minimum number of colors, which is called game chromatic number and is denoted by χgG, while Bob's goal is to prevent Alice's goal. In this paper, we investigate the game chromatic number χgG of Generalized Petersen Graphs GPn,k for k≥3 and arbitrary n, n-Crossed Prism Graph, and Jahangir Graph Jn,m.


---

## Body

## 1. Introduction

n 1981, Brams invented the game as a tool to provide a theoretical proof of the Four Color theorem without using computers [1]. But, it soon became apparent that there were many planar graphs which had game chromatic numbers greater than 4. In 1991, Bodlaender reinvented the game as a two-person game, Alice and Bob [2]. Players take turns coloring the vertices of a given finite graph G=V,E and a color set X=1,2,…,k. Alternately, players take turns over the elements of the set V; Alice starts the game, and her goal is to color the vertices with only k=X colors, while Bob's goal is to prevent her. Bob wins the game if at any stage there are some vertices without available colors. The game chromatic number of a graph G, denoted by χgG, is defined as the smallest integer k such that Alice has a winning strategy on only k colors. In [3], Faigle et al. proved that χgT≤4 for a tree graph. In [4], Guan and Zhu introduced an upper bound to the game chromatic number of outerplanar graphs, which is χgOP≤7. In [5], Bartnicki et al. studied the game chromatic number for the Cartesian product of two graphs. In [6], Sia studied the game for some families of Cartesian product graphs. Raspaud and Wu proved that χgC2mCn=5⟶χgC2m□Cn=5 [7].In [8], Shaheen et al. investigated the game chromatic number for some special circulant graphs and Generalized Petersen Graphs when k=1,2,3.The Coloring Number was defined in [9] as the following:LetΠG be the set of linear orderings on the vertex set of a graph G, and let L∈ΠG. For a vertex v∈VG, the back degree of v with respect to L is the number of its neighbors that precede it in L, i.e., bvtn=q|hNL+v⟶bv=|NL+v| where NL+v=u∈Nvandu<Lv. The back degree of L is the maximum back degree of the vertices in L. The coloring number of G denoted by colG is 1+b where b is the minimum back degree of a linear ordering L over all L∈ΠG, i.e., colG=1+minL∈ΠGmaxv∈VGbv. Clearly, χG≤colG.The Game Coloring NumbercolgG is the competitive version of the coloring number, which was introduced for the first time by Zhu in [10] to give an improved upper bound of the game chromatic number of planar graphs. The game coloring number is a two-person game, which is played by Alice and Bob, who alternate turns and with Alice starting first. After every move, a vertex is selected (among the remaining vertices) and is added to the end of the linear ordering which was formed by previous moves. After selecting all the vertices, a linear ordering L of VG is obtained, let b be its back degree and then colgG=1+b. Alice's goal is to minimize the back degree b, while Bob's goal is to maximize it. Both players use their optimal strategies to form L.A combinatorial game is a finite two-player game with perfect information and no chance. The game coloring number and the game chromatic number are combinatorial games [11].In 2009, Kierstead and Kostochka were the first to present an application of coloring games to a nongame problem, which was the graph packing problem [12].Several studies were presented in 2019 and discussed the game chromatic number of some specific graphs [11, 13, 14]. In [14], C. Chamberlin et al. investigated the game chromatic number of G which is a graph produced by subdividing each edge of GPn,k with n large enough and gcdn,k=1.The uncolored vertexv is called critical vertex if there is just one available color c and there are some uncolored neighbors of v which can be signed with c. In any stage of the game, if there are some critical vertices in Bob's turn, then he wins the game. Also, if there are critical vertices in Alice's turn, then she must defend them by her turn [7].We denote theith turn of Alice by Ai and denote the process of assigning the vertex v with the color c by v⟵c.Tow vertices are adjacent if there is an edge joining them together. For a vertexv in the graph GV,E, the open neighbor set is defined as Nv=u∈V;∃uv∈E and the degree of v is ρv=|Nv⟶ρv=|Nv. A graph G=V,E is r-regular if ρv=r for every v∈V.Definition 1.
Let the integerk,n satisfy k<n/2; Generalized Petersen Graph GPn,k is the graph whose vertex set is V∪U where V=v1,...,vn and U=u1,...,un and its edge set is E=vivi+1,viui,uiui+k, where i=1,2,...,n and subscripts are reduced modulo n.Definition 2.
For a positive even numbern≥4, n-crossed prism graph G=V,E is a graph obtained by taking two distinct cycles, outer cycle Cn1 where VCn1=u1,…,un, and the inner one Cn2 where VCn2=v1,…,vn and adding edges between them as uivi+1,ujvj−1;i∈1,3,…,n−1,j∈2,4,…,n.Definition 3.
Jahangir graph,Jn,m for m≥3, is a cycle Cnm with adding one vertex v0 adjacent to m vertices of Cnm which are at distance n from each other in Cnm.Definition 4.
Then-sunlet graph Sn is a cycle Cn where VCn=u1,u2,…,un with n additional vertex v1,v2,…,vn, and viui∈ESn for i=1,...,n.Proposition 1 (see [10]).
χgG≤colgG.Proposition 2 (see [15]).
The game chromatic number of thewheel graphWn is χgWn=4.Theorem 1 (see [8]).
Forn≥6 and k∈1,2,3, we have χgGPtn,k=4⟶χgGPn,k=4.


## 2. Main Results

In this section, we investigate the game chromatic number of generalized Petersen graph,n-crossed prism graph, and Jahangir graph.Lemma 1.
Forn≥9 and k≥2, every Generalized Petersen graph GPn,k has S8 as a subgraph like the graph in Figure 1.The proof comes clearly from the definition of the Generalized Petersen graph.Figure 1
S8 as subgraph of GPn,k.Theorem 2.
Forn≥9andk≥4, the game chromatic number of the Generalized Petersen Graph GPn,k is χgGPn,k=4.Proof.
Generalized Petersen Graphs are 3-regular graphs; therefore,χgGPn,k≤Δ+1=4. For k∈1,2,3, χgGPn,k=4 is proven in Theorem 1.
Now, by contradiction, we will prove that Player A does not have any winning strategy for any integerk≥4.
Suppose that we have a color setC=1,2,3; by using Lemma 2.1, we notice that, in GPn,k, there is the subgraph as the graph in Figure 1.
Whatever the vertex is chosen by player A to start with, we will get the same state, so without loss of generality assume that player A starts the game withv1, i.e., A1:v1⟵1 then B1:uk+1⟵2; now, u1 is a critical vertex so player A will defend it by coloring it with the third color or coloring its unique uncolored neighbor with a legal color, and whatever his choice for A2 is, then B2:vk⟵1 which means that the vertex vk+1 will become a critical vertex and also player A will have to defend it so whatever his choice is for A3 then B3:un⟵2 and now there are two critical vertices uk,vn and player A cannot defend them together so three colors are not enough for the first player to have a winning strategy. Then, 3<χgGPn,k=4.Theorem 3.
Forn≥6, let G be a n-crossed prism graph, and the game chromatic number of G is χgG=4.Proof.
χgG≤4 since ΔG=3; therefore, we are going to contradict that three colors are not sufficient. Let X=1,2,3 and A1:v1⟵1; then, B1:v3⟵2, and now, v2 is a critical vertex so Alice is forced to defend it in only two ways. We will discuss Alice's second turn A2 as follows:Case 1.A2:v2⟵3 then B2:u2⟶u3, that gives two critical vertices u2,v4 and Alice cannot defend them at the same timeCase 2.A2:u1⟵c where c∈1,2Subcase 2.1. c=1 then B2:vn−1⟵2 then un,vn will be critical vertices and Alice cannot defend them at the same timeSubcase 2.2. c=2 then u2 will become a critical vertex during Bob's turn who will color u3 with the color 3, and Alice loses the game
That meansχgG>3, so χgG=4.Theorem 4.
Form≥3, let G≅Jn,m be the Jahangir graph, and the game chromatic number(1)χgG=4,ifn=1orn=2andm≠3,3,ifn=2andm=3orn≥3andm≥3.Proof.
First, because the Jahangir graph can be divided into cycles, then it is easy to show thatχgJn,m>2. Now, we will discuss the following cases.Case 1. n=1orn=2andm≠3Subcase 1.1.n=1 then G≅Wm, and using Proposition 1, χgG=χgWm=4.Subcase 1.2.n=2 and m≠3 then three colors are not sufficient because if we suppose the color set X=1,2,3 and A1:v0⟵1 then B1:v2⟵2, then there will be two critical vertices v1,v3, and Alice cannot defend them together on her next turn, so she loses the game.Case 2.n=2andm=3orn≥3andmisarbitrarySubcase 2.1. When n=2andm=3, as it is shown in Figure 2.Ifn=2 and m=3, Alice can defend any critical vertices with three colors even with Bob's strategy which was mentioned in Subcase 1.2. We can explain Alice's winning strategy as follows: let the color set be X=1,2,3 and A1:v0⟵1 then B1:v2⟵2, so there will be two critical vertices v1,v3, and then when Alice chooses the next move to be A2:v5⟵3; therefore, Bob cannot use the color 3 on the vertices v4,v6 to win the game and Alice wins with only three colors.Subcase 2.2. When n≥3andm≥3.
We will use the game coloring number as a tool to investigate the upper bound ofχgJn,m.
LetD2=v∈V|ρv=2 and D3=v∈V|ρv=3. The chosen vertex set is C=v∈D3|vis a added toL.
At the beginning, Alice chooses the central vertexv0. Bob chooses a vertex v∉L. Alice follows the next strategy to respond.(1)
Ifv∈D2and∃u∈Nv∩​D3andu∉L then Alice adds u to L(2)
Else, ifv∈D2 and ∃u∈D3C⟶∃u∈D3\C then Alice chooses u and adds it to L(3)
Else, Alice chooses any unchosen vertexu
Using this strategy onJn,m in case n≥3 produces an optimal linear order L with back degree b=maxv∈LNL+v=2. So, colgJn,m=b+1=3, and then, χgJn,m≤3 by using Proposition 1. Therefore, χgJn,m=3 since χgJn,m>2.Figure 2
Jahangir graphJ2,3.



---

*Source: 6475427-2020-04-14.xml*