Game Chromatic Number of Generalized Petersen Graphs and Jahangir Graphs

Abstract

Let G=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.