| In 1991, H.L.Bodlaender posed the concept of game chromatic number of graphs. Let G be a simple graph, and t be a negtive integer, and X be a set of colors. Consider a two-person game on G as following: Player 1 (Alice) and Player 2 (Bob) make moves alternatively with Player 1 moving first. Each feasible move consists of choosing an un-colored vertex, and coloring it with a color from X such that the coloring is proper, i.t. any two adjacent vertices recieve the different color. The game ends as soon as one of the two players can no longer execute any fesible move. Player 1 wins if all the vertices of G are colored, otherwise player 2 wins. The game chromatic number Xg(G) of G is the least integer t such as Player 1 has a winning strategy for |X| =t.Chen Schelp and Shreve introduce a new game chromatic and game chromatic number. Motivated by the game chromatic number Xg(G), the game chromatic number II X_g~*(G) of graph G is developed. We also give the difference of the two game chromatics and the property of the game chromatic number â…¡. By labeling the vertices of a graph with colors, this paper determinates the game chromatic number II of cycle and other graphs related to cycle such as the wheel graphs and the fan graphs, and their subdivision graphs. We simply show the game chromatic number of Mycielski's graph.In chapter one and chapter two, we introduce some basic concepts and some basic Lemmas; In chapter three, we give the game chromatic number II of some graphs such as the path P_n and the cycle C_n. We obtainIn chapter four, we obtain the game chromatic number II of cycles and other graphs related to cycle such as the wheel graphs and the fan graphs, and their subdivision graphs,their r-corona graphs. If n > 3, for the fan graph Fn and the wheel graph Wn, we have 3, n<6. f 3, n = 4, 6, 4, n > 7; 14. otherwise.For the subdivision graph Qn and Gn, we giveX*9(Qn) = 3; x*g(Gn) = 3;For Wn and Fn, we have{3. n = 4 or n = 6 and r is even, 4. otherwise;{3, n < 5 or n = 6 and r is even, 4, otherwise.In chapter five, we simply show the game chromatic number II of Mycielski's graphs. We prove that the game chromatic number II of the complete graph Kn is n + 1, the game chromatic number II of the complete bipartite graph Kmt n is 3; Also for Mycielski'sgraphs, we have3, n < 5,4, n>6.At last, we post a conjecture on the game chromatic number n of the Mycielski's graphs of the cycle Cn: for n > 5, xï¿¡(/i(Cn)) = 4. |
