Research ArticleOpen AccessGoogle Scholar indexed
Game Chromatic Number of Some Regular Graphs
Department of Mathematics, Tishreen University, Lattakia, Syria
Department of Mathematics, Tishreen University, Lattakia, Syria
Department of Mathematics, Tishreen University, Lattakia, Syria
- 1 Department of Mathematics, Tishreen University, Lattakia, Syria
- 2 Department of Mathematics, Tishreen University, Lattakia, Syria
- 3 Department of Mathematics, Tishreen University, Lattakia, Syria
Open Journal of Discrete Mathematics·Volume 09 (2019)·Pages 159–164·Published 9 August 2019·DOI10.4236/ojdm.2019.94012
Copy link · social · email
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 C n (1,2), , and generalized Petersen graphs GP ( n ,2), GP ( n ,3).
KeywordsGame Chromatic NumberCirculant GraphGeneralized Petersen Graphs
- 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
- 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
- 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
- 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
- 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.
- 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.
- 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.