On game coloring of graphs

Abstract

This thesis primarily deals with graph coloring game, graph edgecoloring game and oriented graph coloring game. Let G be a finite graph andX be a set of n colors. The graph coloring game on G is defined to be a gameplayed by two players Alice and Bob with Alice start playing the game first.They take turns alternatively to color the vertices of G using colors from X suchthat no two adjacent vertices are colored with the same color. Alice wins the newlinegame if it is possible to color all the vertices of G with colors from X. Bob winsif at any point of the game, there is a vertex which cannot be colored with colorsfrom X. We always assume that both the players play optimally. The gamechromatic number of G, denoted by cg(G), is the minimum number of colorsneeded in the color set X for which Alice has a strategy to win.In Chapter 2, we have determined the game chromatic number of the direct product of (i) two stars K1;n and K1;m, (ii) two complete bipartite graphsKm;n and Ka;b, (iii) path Pn and star K1;m, (iv) path P2 and cycle Cn and (v) pathP2 and wheelWn. In Chapter 3, we discuss the game chromatic number of thelexicographic product of graphs. Given any two simple graphs G and H, we gavean upper bound for the game chromatic number of the lexicographic productof G and H. Also, we have determined the game chromatic number of thelexicographic product of (i) path P2 with path Pn, (ii) path P2 with star K1;n and(iii) path P2 with wheelWn. newline newline