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).
References
[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.
https://doi.org/10.1007/3-540-53832-1_29
[2]
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
[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. https://doi.org/10.1016/j.disc.2015.12.010
[4]
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
[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.
![\"\"](\"Edit_052ffcd3-c66b-405b-b393-dc3597a0fc35.bmp\")
, and generalized Petersen graphs GP(n,2), GP(n,3).
