OJDM  Vol.9 No.4 , October 2019
Game Chromatic Number of Some Regular Graphs
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 Cn(1,2), , and generalized Petersen graphs GP(n,2), GP(n,3).
Cite this paper: Shaheen, R. , Kanaya, Z. and Alshehada, K. (2019) Game Chromatic Number of Some Regular Graphs. Open Journal of Discrete Mathematics, 9, 159-164. doi: 10.4236/ojdm.2019.94012.

[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.

[2]   Raspaud, A. and Wu, J. 2009) Game Chromatic Number of Toroidal Grids. Information Processing Letters, 109, 1183-1186.

[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.

[4]   Heuberger, C. (2003) On Planarity and Colorability of Circulant Graphs. Discrete Mathematics, 268, 153-169.

[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.